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