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

문제

문제 보러 가기

풀이

계속해서 재귀와 백트래킹 문제를 풀고 있는데, 문제 유형이 조금만 달라져도 풀기가 어려워지는 것이 느껴진다. 이 문제의 경우, 어떤 값에 대해서 추가할지 아닐지를 정해나가는 문제이기 때문에 그 두 가지 경우에 대해서 모두 재귀함수를 호출하면서 반복해나가는 형태라 떠올리기 힘들었다. 재귀와 백트래킹 문제를 계속해서 풀어봐야겠다.

"use strict"

const [[n, s], inputs] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(str => str.split(' ').map(Number));

function solution(n, s, inputs) {
    let answer = 0;

    function backTracking(k, sum) {
        if (k === n) {
            if (sum === s) answer++;
            return;
        }
        backTracking(k+1, sum);
        backTracking(k+1, sum+inputs[k]);
    }

    backTracking(0, 0);

    if (s == 0) answer--;

    return answer;
}

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