백준 14225 부분수열의 합2 (부분집합)

문제

제한 사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const sol = (input) => {
  const n = +input[0];
  const arr = input[1].split(" ").map(Number);
  let sumArr = new Array(200001).fill(0);
  const dfs = (L, sum) => {
    if (L === n) {
      sumArr[sum] = 1;
      return;
    } else {
      dfs(L + 1, sum);
      dfs(L + 1, sum + arr[L]);
    }
  };
  dfs(0, 0);

  for (let i = 1; i < 2000001; i++) {
    if (!sumArr[i]) {
      return i;
    }
  }
};

console.log(sol(input));

• 큰 수로 배열하나를 만들고 0로 초기화 한다.
• 부분집합 알고리즘(dfs)로 부분집합의 합을 전부 구하고 배열의 해당 인덱스의 값을 1로 바꾼다.
• 값이 0인 가장 작은 i를 리턴한다.