[백준] 1182번 부분수열의 합 - JavaScript(NodeJS)

문제

1182번: 부분수열의 합

 

풀이

정수 N개를 가지고, 모든 부분수열을 구한다.
부분수열 원소들의 합이 S가 되는 부분수열의 개수를 출력한다.

 

N개의 정수를 배열에 받아서 dfs를 실행한다.

 

부분수열을 만족하기 위해서
재귀의 매 단계에서 L번째 정수를 선택하거나, 선택하지 않는 두가지 경우를 모두 조회해보면 된다.

 

코드

const sol = (input) => {
  const [N, S] = input[0].split(" ").map(Number);
  input = input[1].split(" ").map(Number);
  let count = 0;

  const pick = [];
  function dfs(L) {
    if (L === N) {
      const sum = pick.reduce((sum, val) => sum + val, 0);
      if (sum === S) count++;
      return;
    }
    pick.push(input[L]);
    dfs(L + 1);
    pick.pop();
    dfs(L + 1);
  }
  dfs(0);

  if (S === 0) count--; // pick이 아무것도 선택하지 않았을 때 sum=0이므로 정답보다 1이 더 크므로, 감소시켜준다.
  return count;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });