[알고리즘] 합이 같은 부분집합(DFS)

문제

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

 

입력설명

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

강사님 문제풀이

function solution(arr){
    let answer = 'NO';
    const arrSum = arr.reduce((acc,cur)=> acc+cur,0);
    const n = arr.length;
    let flag = 0;
    function DFS(L,sum){
        if(flag) return;
        if(L===n){
            if((arrSum-sum)===sum) {
                answer = 'YES';
                flag = 1;
            }
        }
        else{
            DFS(L+1,sum+arr[L]);
            DFS(L+1,sum);
        }
    }
    DFS(0,0);

    return answer;
}

let arr=[1, 3, 5, 6, 7, 10];
console.log(solution(arr));

• 두 부분집합은 서로소 집합으로, 한 부분의 합이 다른 나머지의 합과 같으면 정답
• 나머지의 합은 (모든 원소의 합 - 부분집합의 합)으로 구할 수 있다.
• DFS 탐색을 통해 해당 원소의 포함, 불포함 여부를 가려 sum을 구할 수 있다.
• 탐색 레벨이 배열의 길이에 도달하면, 합의 일치 여부를 판단한다.
• 답을 찾았을 때, flag 변수를 1로 변경해 불필요한 재귀를 끝낼 수 있도록 한다.

나의 오답

function DFS(n){
    let tmp = 0;
    if(n>=arr.length){
        for(let i = 0; i<arr.length; i++){
            if(visited[i]===1) tmp+=arr[i];
        }
        if(tmp>0)cnt.push(tmp);
    }
    else{
        visited[n]=1;
        DFS(n+1);
        visited[n]=0;
        DFS(n+1);
    	}
	}

    //i번 만큼 DFS 함수를 호출한다. 
    for(let i = 0; i < arr.length; i++){
        if(i>=arr.length){
            return;
        }
        else {
            DFS(i);
        }
    }

    //cnt배열과 cnt의 Set 콜렉션의 길이를 비교해 중복 여부를 판단한다. 
    const hasDup = new Set(cnt).size != cnt.length;
    if(hasDup){
        return 'YES';
    }
    
    return answer;
}

let arr=[1, 3, 5, 6, 7, 10];
console.log(solution(arr));

• 처음 접근은 부분집합이 되는 모든 원소의 합을 배열로 만들어, 중복된 값이 있으면 정답으로 간주하는 것이었다.
• 답을 쓰고 문제를 보니, 각 부분집합은 서로 겹치지 않는 서로소 집합임을 간과하였음을 깨달았다.
• 아무튼 내 접근법은 방문 여부를 확인해 모든 부분집합의 경우의 수를 만들고, 이 배열의 길이가 Set 컬렉션의 길이와 비교해 달라지면 중복으로 간주하는 것이다.
• 문제를 읽고 파악하는 시간을 좀 오래 가져야 할 것 같다. 흑흑 흑흑흑