[Algorythm][JS][DFS] 합이 같은 부분집합

GY·2021년 12월 26일
0

알고리즘 문제 풀이

목록 보기
82/92

문제

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


풀이

보통 Level을 뜻하는 L을 변수로 많이 사용한다고 한다.
부분집합의 합을 구하는 문제이므로 L에 해당하는 숫자를 각 Level마다 합계에 더해준다.

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(arr){
                let answer="NO", flag=0;
                let total=arr.reduce((a, b)=>a+b, 0);
                let n=arr.length;
                function DFS(L, sum){
                    if(flag) return;
                    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));
        </script>
    </body>
</html>

flag 변수는 특별한 건 아니고, 답을 이미 찾았을 경우 불필요한 순회를 멈추기 위한 변수인데, 초기값은 0이었다가 답을 찾으면 1이 된다. 이 변수를 조건에 넣어 0일때만 순회를 계속하도록 해주었다.

Reference

  • 인프런 - 자바스크립트 알고리즘 문제풀이(김태원)
profile
Why?에서 시작해 How를 찾는 과정을 좋아합니다. 그 고민과 성장의 과정을 꾸준히 기록하고자 합니다.

0개의 댓글