합이 같은 부분집합

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때

두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

내 풀이 

부분집합을 dfs로 구한 게 배열합의 절반이면 되는거 아닌가? 라고 생각해서 구해봤는데 테스트 케이스에서 걸리는 게 있었고 원인을 찾지 못했다..

import java.util.*;


public class Main{
    static int cnt = 0;
    static int[] arr, ch;

    static String ans = "NO";

    public void dfs(int v){
        if (ans == "YES") return;

        if (v == arr.length){
            for (int i = 0; i < arr.length; i++){
                if(ch[i] == 1) cnt -= arr[i];
            }
            if (cnt == 0 ) ans = "YES";
            cnt = Arrays.stream(arr).sum()/2;
        }

        else {
            ch[v] = 1;
            dfs(v+1);
            ch[v] = 0;
            dfs(v+1);
        }


    }

    public static void main(String args[]) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        arr = new int[n];
        ch = new int[n];
        cnt = Arrays.stream(arr).sum()/2;
        for (int i =0; i< n; i++) arr[i] = in.nextInt();
        T.dfs(0);

        System.out.println(ans);
    }
}

 

강의 풀이 

 

sum을 dfs함수에 저장해두고 (total - sum) == sum 으로 합이 홀수일때도 판별 가능하게 저장해둔다

ch배열이 없이도 sum에 배열의 해당 인덱스 값을 더한 경우와 더하지 않은 경우를 만들 수 있다.

import java.util.*;


public class Main{
    static int total = 0;
    static int[] arr;

    static String ans = "NO";


    public void dfs(int v, int sum){
        if (ans == "YES") return;
        //sum이 집합 전체의 절반보다 크면 불가능하니 바로 리턴
        if (sum > total/2) return;

        if (v == arr.length){
            if((total - sum) == sum){
                ans = "YES";
            }
        }

        else {
            dfs(v+1, sum + arr[v]);
            dfs(v+1, sum);
        }


    }

    public static void main(String args[]) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        arr = new int[n];
        for (int i =0; i< n; i++) {
            arr[i] = in.nextInt();
            total += arr[i];
        }
        T.dfs(0, 0);

        System.out.println(ans);
    }
}