[백준 1182 - Node.js] 부분수열의 합

문제 링크

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

풀이

const [ N, S, ...arr ] = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).map(v => +v);

const solve = (N, S, arr) => {
  let output = 0;
  const recursion = (i, sum) => {
    if (i === N) return;

    sum += arr[i];
    if (sum === S) output++;

    recursion(i + 1, sum);
    recursion(i + 1, sum - arr[i]);
  };

  recursion(0, 0);
  console.log(output);
};

solve(N, S, arr);

recursion은 다음과 같이 동작한다.

 

recursion은 고를 숫자의 인덱스(i)와 지금까지 고른 숫자들의 합(sum)을 인수로 받는다.

 

i 번째 숫자를 고르고 sum에 더한다.

 

sum이 S와 같다면 output을 증가시킨다.

 

다음에 고를 숫자의 인덱스(i + 1)과 지금까지 고른 숫자들의 합(sum)을 recursion의 인수로 넣어 재귀호출한다. 즉, arr[i]를 고르고 arr[i+1]을 고르는 과정으로 넘어간다.

 

다음에 고를 숫자의 인덱스(i + 1)과 지금까지 고른 숫자들의 합(sum)에서 이번에 고른 i번째 숫자를 뺀 값을 recursion의 인수로 넣어 재귀호출한다. 즉, arr[i]를 고르지 않고 arr[i+1]을 고르는 과정으로 넘어간다.

 

이렇게 하면 0부터 N-1번째 까지의 수를 하나씩 고르거나 고르지 않거나 하면서 모든 경우를 다 탐색하게 된다.