문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력

5 0
-7 -3 -2 5 8

예제 출력

1

내가 했던 풀이 방법

DFS 함수는 sum과 prev 값을 전달 받는다. sum이 S가 되면 count를 1 증가시킨다. (여기서 return을 시키지 않는 이유는 현재까지의 요소를 이용해 S가 될 수도 있지만, 그 뒤의 요소들을 조합해 또 다른 S를 만들 수 있기 때문이다.) prev 이후의 값들을 sum에 더하거나 더하지 않아줌으로써 새로운 부분수열을 조합한다. i가 N-1이 되어버리면 재귀가 종료된다.

부분수열의 크기가 양수이어야 하므로 DFS는 0, 0을 전달하는 것이 아닌 array[i]와 i를 전달해주었다.

코드

const fs = require('fs');
let [n, array] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');
array = array.trim().split(' ').map(Number);

let N = Number(n.trim().split(' ')[0]);
let S = Number(n.trim().split(' ')[1]);

let count = 0;

function DFS(sum, prev) {
  if (sum === S) {
    count++;
  }

  for (let i = prev + 1; i < N; i++) {
    DFS(sum + array[i], i);
  }
}

for (let i = 0; i < N; i++) {
  DFS(array[i], i);
}

console.log(count);

회고

return을 신경 쓸 필요가 없었다는 것에 충격 하지만 더 충격인 건 DFS 정말 많이 풀어봤음에도 당연한 논리적인 흐름을 놓치고 문제를 풀었다는 것이다... DFS(sum+array[i], i)에서 다음 for문으로 넘어가면 자연스럽게 i번째 요소를 더해주지 않았다는 것이 되는데 그 부분을 간과하고 짜고 DFS(sum, i)를 추가해서 중복 계산이 발생하게 만들었다... 진짜 당연한 부분인데 그렇게 코드를 짜서 삽질을 조금 했다..