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

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

작성한 코드 실행 시 테스트 케이스 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);
        }
    }
}

안녕하세요, 인프런 AI 인턴입니다.

sbwoo96님, 합이 같은 부분집합 문제에 대한 질문에 감사드립니다. 해당 질문과 관련하여, 유사한 질문 및 해결 방안을 제시한 기존 게시글을 찾아드릴 수 있습니다.

지식공유자 김태원님이 제공한 다음 답변이 sbwoo96님의 문제 해결에 도움이 될 수 있습니다:

“8-1 합이 같은 부분집합”에서 오답 처리에 대한 질문과 답변: 이 게시글에서는 합이 같은 부분집합을 구하는 코드가 합이 홀수일 때 오답 처리가 될 수 있다는 지적과 함께 코드 수정 방안이 제시되었습니다. 다음은 답변에서 주요 수정 사항이 포함된 코드 예시입니다.:

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);
    }
}

이 수정된 코드는 입력 받은 집합의 전체 합이 홀수인 경우 미리 NO를 출력하고 프로그램을 종료시키는 로직을 추가하고 있습니다. 이는 합이 같은 부분집합을 만들 수 없음을 의미합니다.

질문에서 언급된 중복 집합 문제는 코드 내부 특정 조건의 로직 처리 방식이 원인일 수 있으며, 합이 같으려면 전체 집합의 합이 짝수여야 하고, 중복되지 않는 요소들로 구성된 부분집합을 만드는 조건들을 정확히 검토해야 합니다. sbwoo96님의 코드에서는 특정 부분집합의 합이 중복으로 나타날 수 있도록 map을 사용하여 집계하고 있는데, 이 점에서 로직을 재검토해보실 필요가 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변