[Algorithm] 합이 같은 부분집합(DFS)

❐ 합이 같은 부분집합

▶︎ 문제

    N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력하는 프로그램을 작성하세요.
    둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 

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

 

▷ 입력 예제

1 3 5 6 7 10

 

▶︎ 출력 예제

YES

 

▷ 내 답안

function solution(arr) {
    let answer = "NO";
    let ch = Array.from({ length: arr.length + 1 }, () => 0);
    function DFS(v) {
        if (v === arr.length + 1) {
            let sum_1 = 0;
            let sum_2 = 0;
            for (let i = 1; i <= arr.length; i++) {
                if (ch[i] === 1) {
                    sum_1 += arr[i - 1];
                } else {
                    sum_2 += arr[i - 1];
                }
            }
            if (sum_1 === sum_2) {
                answer = "YES";
                return answer;
            }
        } else {
            ch[v] = 1;
            DFS(v + 1);
            ch[v] = 0;
            DFS(v + 1);
        }
    }
    DFS(1);
    return answer;
}

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

 

문제를 푸는 기본원리는 부분집합 구하기에서 벗어나지 않는다. 이 문제는 함수를 종료하는 조건을 좀 더 추가하면 쉽게 해결할 수 있다.

 

let answer = "NO";

변수 answer의 기본값은 NO로 설정해둔다. 모든 경우의 수를 돌리다가 두 부분집합의 합이 같은 경우가 생기면 answer의 값을 YES로 변경하고 함수를 종료한다. 함수가 다 끝날때까지 합이 같은 경우가 나타나지 않는다면 값이 NO인 answer가 return되면서 함수가 종료될 것이다.

 

if (sum_1 === sum_2) {
    answer = "YES";
    return answer;
}

변수 sum_1과 sum_2는 분리된 서로소 집합의 합을 나타낸다. 이 둘의 합이 같을 경우 answer의 값이 YES로 변경된다.

 

이전 포스팅인 부분집합 구하기와 마찬가지로 전위 순환을 통해 만들 수 있는 부분 집합들을 출력해보면 다음과 같다.

6개의 인자를 가지므로 2의 6승인 64개의 부분 집합이 콘솔 창에 나타나는 것을 확인할 수 있다.

 

여기서 주의해야 할 것은 인자로 들어온 배열 arr는 길이가 6이고 index 0부터 값이 채워지는 반면, 우리가 카운트를 체크하기 위해 만든 ch라는 배열은 길이가 길이가 n+1 인 7이고 index가 1일 때부터 값이 적용된다는 것이다.

 

for (let i = 1; i <= arr.length; i++) {
    if (ch[i] === 1) {
        sum_1 += arr[i - 1];
    } else {
        sum_2 += arr[i - 1];
    }
}

따라서 for문은 index 값이 1부터 6까지 총 6번을 탐색하게 되며 우리가 arr에서 가져와야 할 값은 index 0부터 5가 되므로 arr[i-1]으로 코드를 짜야한다. 

 

내 코드와 강사님의 코드를 확인해보니 내 코드의 길이가 좀 더 길었고 배열마다 index 0의 유무가 달라서 구현할 때 혼란스럽기도 했다. 코드에 개선의 여지가 있다고 느꼈다. reduce 메서드를 활용해서 추후에 한 번 더 풀어보자.

 

 

이 포스팅은 인프런 강의에서 제공하는 솔루션이 아닌 제가 사용한 코드를 설명하는 글입니다. 
더 자세한 설명과 확실한 답을 원하신다면 인프런 강의를 확인하세요!