2022/03/31) 5. 합이 같은 부분집합 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<합이 같은 부분집합>
: N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두개의 부분집합으로 나누었을 때 두 부분집합의 원소와 합이 서로 같은 경우가 존재하면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력하는 프로그램을 작성한다. 둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 한다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10}으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
! 서로소라는 단어가 들어가서, 서로소인 집합들 / 서로소가 아닌 집합들로 분리해야 한다고 문제를 잘못이해했었다. 이게 아니고 Disjoint Set은 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합이라는 거다. 이 말은 곧, 각 원소들은 하나의 집합에만 속한다는 말이다.

2. 해결 방법

1. level로 점차 내려가야 한다. arr[0]이 포함되거나(O) 되지 않거나(X)를 표현하려면, level 0에서 두 갈래로 나뉘어져야 하는데, 이 갈래는 L+1로 표현(L에는 0을 삽입)한다.
   그리고 포함된다면 sum에 sum+arr[L]을 넘겨주고, 포함되지 않는다면 sum을 넘겨준다.
   그리하여 DFS(L+1, sum+arr[L])과 DFS(L+1, sum)가 되는거다.
2. 그렇다면 위의 내용을 참고하여, if문의 조건을 달아야 하는데, arr배열은 인덱스가 0~5까지 있으므로 만약 인덱스 5번의 포함유무를 판단하려면, DFS(5+1, )(=DFS(L+1, ))이 될 것이다. 그리하여 L이 6이 된다면 모든 원소가 다 부분집합에 포함된 상태이므로 이제 확인을 해야한다.
3. total이라는 변수에 배열들의 합을 reduce로 구해놓고, (total-sum)===sum이 된다면 answer="YES"; flag=1;을 해준다. (flag가 있는 이유는, 스택에 남아 있는 함수들만 호출되고 다른 재귀호출은 없이 끝나도록 하기 위해서임)
   ! 부분집합구할때의 원리와 비슷한 거 같다~ 하 스택프레임으로 그림을 못그리겠네.. 어렵다

3. 정답

        <script>
            function solution(arr){
                let answer="NO", flag=0;
                let total = arr.reduce((a,c) => a+c, 0);
                let n = arr.length; 
                function DFS(L, sum){
                    if(L===n){ //6
                        if(flag) return;
                        if((total-sum)===sum){
                            answer ="YES";
                            flag=1;
                        } 
                    }
                    else{
                        DFS(L+1, sum+arr[L]); //포함될 때(o) : sum에 누적, ex : L(5)+1 => 인덱스 5가 포함될 때
                        DFS(L+1, sum); //포함되지 않을 때(o), ex : L(5)+1 => 인덱스 5가 포함되지 않을 때 
                        //위의 주석 내용을 정리하면, L(6)+1<L이 6이 됐을 경우>엔 인덱스 6이 포함/포함되지 않았을 때를 구하는 것이므로 L이 6일 땐 종료해야한다.
                    }
                }
                DFS(0, 0);
                return answer;
            }
            let arr=[1, 3, 5, 6, 7, 10];
            console.log(solution(arr));
        </script>