백준 1182 부분수열의 합 (백트래킹)

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let [n, s] = input.shift().split(" ").map(Number);
let numbers = input.shift().split(" ").map(Number);
const solution = (n, s, numbers) => {
  let answer = 0;
  const dfs = (L, sum) => {
    if (L === n) {
      if (sum === s) {
        answer++;
      }
      return;
    } else {
      dfs(L + 1, sum + numbers[L]);
      dfs(L + 1, sum);
    }
  };
  dfs(0, 0);
  if (s === 0) {
    answer--;
  }
  return answer;
};

console.log(solution(n, s, numbers));

• 부분 집합 알고리즘
• s가 0일 경우에만 -1해주는데 그이유는 아무것도 포함안한것 부분집합의 합이 0이기 때문에 그것은 제외해준 것이다.