합이 같은 부분 집합 문제 질문 드립니다.

안녕하세요, 강의 잘 듣고 있습니다.

작성한 코드 실행 시 테스트 케이스 4번에서만 오답처리 되어 확인을 해봤습니다.

4번째 테스트 케이스인 9, [3 6 13 11 7 16 34 23 12] 를 입력한 후 디버깅을 해본 결과

실제로 중복집합이 발생하는 것으로 확인됐습니다.

제 코드 상에 어떤 부분이 문제가 됐는지 알고 싶습니다.

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int level;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        int max = 0;

        int dep[] = new int[size + 1];

        level = size;

        for (int i = 1; i < dep.length; i++) {
            int val = sc.nextInt();
            dep[i] = val;
            if (val > max) {
                max = val;
            }

        }

        int[] check = new int[max + 1];

        Map<Integer, Integer> map = new HashMap<>();

        dfs(1, check, dep, map);

        Collection<Integer> values = map.values();

        boolean duplicate = false;

        for (int i : values) {
            if (i != 1) {
                System.out.println("YES");
                duplicate = true;
                break;
            }
        }

        if (!duplicate) {
            System.out.println("NO");
        }

    }

    public static void dfs(int l, int check[], int[] depth, Map<Integer, Integer> map) {
        if (l == level + 1) {
            int sum = 0;
            for (int i = 1; i < check.length; i++) {
                if (check[i] == 1) {
                    sum += i;
                }
            }
            if (sum > 0) {
                map.put(sum, map.getOrDefault(sum, 0) + 1);
                System.out.println("Sum: " + sum + ", Count: " + map.get(sum));


            }
        } else {
            check[depth[l]] = 1;
            dfs(l + 1, check, depth, map);
            check[depth[l]] = 0;
            dfs(l + 1, check, depth, map);
        }
    }
}

import java.util.Scanner;

class Main {
    static int n,total;
    static int[] array;
    static boolean flag;

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

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        total =0;
        array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
            total += array[i];
        }
        if(total % 2 == 1) {
          System.out.println("NO");
          return;
        }
        flag = false;
        T.DFS(0, 0);
        if (flag) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    void DFS(int L, int sum) {
        if (flag || sum > total / 2 || L == n) {
            return;
        }
        if (sum == total / 2) {
            flag = true;
            return;
        }
        DFS(L + 1, sum + array[L]);
        DFS(L + 1, sum);
    }
}