합이 같은 부분집합

합이 같은 부분집합(DFS : 아마존 인터뷰)

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

입력 설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

출력 설명

첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

입력

6
1 3 5 6 7 10

출력

YES

구현 코드

    static String answer = "NO";
    static boolean flag = false;
    static int total = 0;
    static int n;
    static int[] arr;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = in.nextInt();
            total += arr[i];
        }

        dfs(0,0);
        System.out.println(answer);
    }

    static void dfs(int L,int sum){
        if(flag) return;
        if(sum>total/2) return;
        if(L == n){
            if((total - sum)== sum) {
                answer = "YES";
                flag = true;
            }
        }
        else{
            dfs(L+1,sum+arr[L]);
            dfs(L+1,sum);
        }
    }

dfs활용 문제로 처음 문제를 읽었을 때 각 숫자가 포함되지 않는 경우, 포함되는 경우로 나누면서 경우를 따져야겠구나까지는 생각을 했지만.. 어떻게 구현할지 머리가 안돌아가서 모범답안의 힘을 빌린 문제였음.
왜인지는 모르겠는데 재귀를 쓰면 시간을 많이 잡아먹을 거라는 생각에 재귀를 안쓰려고 머리를 더 굴리는 느낌...
재귀로 풀면 간단한 것을...

• 알고리즘

  L : 타고 들어가는 레벨 -> n까지 타고 들어감
  sum : 숫자들의 합
  재귀로 계속 다음단계를 호출하면서 sum을 더해감. 마지막 단계까지 이르렀을때 모든 수의 총합인 total - sum이 sum과 같다면 YES 출력. 아니면 NO 출력.
  flag 변수의 사용 이유는 만약 모든 레벨을 다 돌기전에 정답인 경우가 있으면 그 시점에서 재귀호출을 멈추기 위해서임.
  또한 sum>total/2까지 비교해주는 이유는 sum이 total/2보다 큰 경우 수를 더 포함할 필요가 없어지므로 그 시점에서 종료해야함.

dfs,bfs문제는 개념은 알겠는데 아직도 단시간내에 문제푸는건 잘 안되는 것 같다. 꾸준히 해야겠음