백준 1182 - 부분수열의 합

문제

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

코드

const dfs = (i, sum) => {
  console.log(i, sum);
  if (i >= n) {
    return;
  }
  sum += input[i];
  if (sum === target) {
    result += 1;
  }
  dfs(i + 1, sum - input[i]);
  dfs(i + 1, sum);
};
dfs(0, 0);
console.log(result);

풀이

부분수열의 의미가 여기서는 index 0 1 2 , 2 3 4 이렇게 붙어있는것만 아니라 0 2 4 , 3 4 5 ... 같은것도 다 포함
그래서 항상 배열에서 이 값을 포함할건지 or 포함 안하고 넘어갈건지를 선택해줘야 함