합이 같은 부분집합

문제분석

1. arr의 합을 total이라 했을때
   total - 부분집합 = 부분집합 이면 원소의 합이 같은 경우이다.
2. 완전탐색으로 arr의 최대합부터 최소합을 탐색한다.
3. 탐색도중에 1의 경우가 나오면 재귀함수를 탈출한다.

코드

function solution(arr){
    let total = arr.reduce((a, b) => a+b , 0),
    n = arr.length,
    answer = "No",
    flag = 0;
    
    function DFS(L,sum) {
        if(flag === 1) return;
        else if(L === n){
            if(total-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));

완전탐색의 원리

맨위부터 숫자가 유무로 나누어져 결국 모든 경우의 수를 구하게 된다.

햇갈리는점
else if(L === n)로 끝가지 도달하면 그 전단계로 돌아가 DFS(L+1,sum)을 수행한다.
예를들어 D4의 x인 경우까지 작업을 완료 했다면 D2로 돌아가 x인 경우인 DFS(L+1,sum) 작업을 수행한다.