[JavaScript/백트래킹] 백준 실버 2 : 1182 - 부분수열의 합

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

1182번: 부분수열의 합

---

📌 작성한 코드 

// 1182
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, s] = input[0].split(" ").map(Number);
const list = input[1].split(" ").map(Number);

let answer = 0;
const recursion = (at, sum) => {
    if (at === n) return;
    sum += list[at];

    if (sum === s) {
        answer++;
    }

    recursion(at + 1, sum);
    recursion(at + 1, sum - list[at]);
};

recursion(0, 0);
console.log(answer);

📌 풀이 

부분 수열 : 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열

- 원래 수열이 [1,2,3,4,5]라고 했을 때 [1,2,3], [1,2,5]와 같이 일부를 제외하고도 순서가 똑같은 수열을 말한다.

- 부분 집합과 다른 점은 순서를 지켜야한다는 것이고, 중간의 일부를 제외한 것도 부분 수열이니까 주의해야 한다.

 

매 단계에서 해당 숫자를 더해서 만든 수열과 해당 숫자를 더하지 않은 수열 두가지의 부분에 대한 재귀를 실행한다.

const recursion = (at, sum) => {
    if (at === n) return; 
    sum += list[at]; // 수열의 해당 위치 숫자 더하기

    if (sum === s) { // 합이 s면 답에 추가
        answer++;
    }

    recursion(at + 1, sum); // 현재 숫자를 더한 값에서 재귀함수 호출
    recursion(at + 1, sum - list[at]); // 현재 숫자를 더하지 않은 값에서 재귀함수 호출
};

 

 

✅ 성공