[Javascript] 백준 1182: 부분수열의 합

문제

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

입력

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

출력

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

예제 입력 1 

5 0
-7 -3 -2 5 8

예제 출력 1 

1

 

---

문제 풀이

다른 풀이들을 보면 dfs 내부에서 for문을 돌지않고 문제를 해결합니다. 저는 원래 풀던 방법으로 해결하고 싶어서 모든 경우의 수에 대해 합을 구해서 문제를 해결했습니다.

 

1. dfs는 길이가 M인 부분수열을 만들어냅니다. 해당 문제는 길이가 정해져있지않고, 모든 길이에 대해서 구해야하기 때문에 1부터 주어진 인풋배열의 길이 N까지 dfs를 반복했습니다.

 

2. 해당 문제는 테스트케이스가 한개만 주어지는데, 저는 처음에 풀때 같은 숫자가 들어가는 경우를 제외하고 풀어서 37%에서 계속 틀리더라고요. 가령 인풋배열이 [-7, -3, -2, 0, 0]이고  S가 0이라면, 제가 처음에 풀었을 땐 결과가 2가 나왔습니다. 즉  [0], [0]의 경우만 계산되고 있었던 거죠. 그러나 [0, 0]까지 답은 3이 되어야합니다. 이 부분을 개선하니 정답이 되었습니다.

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, S] = input[0].split(" ").map(Number);

const nums = input[1].split(" ").map(Number);
const visited = Array(N).fill(false);

const sequence = [];
let sum;
let answer = 0;
let M = 1;

const dfs = (count, start) => {
  if (count === M) {
    sum = sequence.reduce((acc, cur) => acc + cur, 0);
    if (sum === S) answer++;
    return;
  }

  for (let i = start; i < N; i++) {
    if (visited[i] === false) {
      sequence.push(nums[i]);
      start++;
      visited[i] === true;
      dfs(count + 1, start);
      visited[i] === false;
      sequence.pop();
    }
  }
};

for (let i = 0; i < N; i++) {
  dfs(0, 0);
  M++;
}

console.log(answer);