[백준] 1182번 : 부분수열의 합

문제

 

---

풀이

 

백트래킹으로 탐색하면서 S가 되는 값이 나오는지 확인하면 된다.

부분수열의 길이가 정해진건 아니라 이와 관련된 종료조건은 딱히 없다.

 

S와 같은 부분수열의 합을 찾자마자 return을 하는 실수를 할 수도 있다.

근데 만약 S=0이고 주어진 정수가 -7 7 -3 3이라면

-7 7도 가능한 부분수열이지만 -7 7 -3 3도 가능한 부분수열이다. 이걸 놓치지 않도록 하자.

---

소스코드

 

#include <iostream>

using namespace std;

int input[20], N, S, sum, cnt;

void backtracking(int idx) {
    for (int i = idx + 1; i < N; i++) { //중복되는 수열을 제거하기 위해
        sum += input[i]; //visited 처리
        if (sum == S) //S와 같다면 cnt++
            cnt++;
        backtracking(i);
        sum -= input[i]; //unvisited 처리
    }
}

int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++)
        cin >> input[i];
    backtracking(-1);
    cout << cnt;
}

중복되는 수열을 만들고 싶지 않아서 인덱스 기준 오름차순으로 탐색하도록 했다.

S와 같은 sum을 발견하면 cnt를 증가해주지만 이 뒤에도 가능한 부분수열이 나올 수 있으므로 탐색은 계속한다.