[백준(BOJ)] 1182번: 부분수열의 합 (백트래킹(Backtracking), C++)

💻 C++ 제출코드

---

#include <stdio.h>
#include <deque>

using namespace std;
int count=0;

void solution(int sum, int index, int target, deque<int> *arr){

    sum += (*arr)[index];

    if(index == (*arr).size()) return;
    if(sum == target) count++;
    
    solution(sum - (*arr)[index], index+1, target, arr);
    solution(sum, index+1, target, arr);
}

int main(){
    int N, S; // N: 정수의 개수, S: 합

    scanf("%d %d", &N, &S);

    deque<int> arr;

    for(int i=0; i<N; i++){
        int num;
        scanf("%d", &num);
        arr.push_back(num);
    }
    
    solution(0, 0, S, &arr); // sum, index, target sum, arr
    printf("%d", count);
    
}

 

 

📝 문제풀이 과정

---

• DFS(sum - arr[index], index + 1)부터 시작하는데, sum += arr[index]를 하고 arr[index]를 빼므로 현재 원소를 제외하고 진행하게 된다. 

• 처음에는 sum이 -7 / -3 / -2 / 5 / 8 이렇게 시작하고, index = 5일 때는 arr[index]에서부터, index != 5까지 sum에 더하게 된다. 따라서 8 / 5 / 5 8 / -2 / -2 5 / -2 5 8 / ... 이렇게 arr[index]부터 시작하는 부분수열을 구할 수 있게된다.

 

WRONG!!!

이렇게 하면 안 된다..

index == N일 때를 먼저 비교해야 이때 아예 나가는데, 이미 sum == S 인 상태에서 또 비교를 하게 되어 count에 또 추가될 수 있다. 이걸 계속 몰라서 20번 제출하고서야 맞았다... 😣

index == N은 정답이 될 수 없는 조건이므로 리턴을 시켜 미리 가지치기를 하는 이것이 백트래킹인 것이다. 

 

 

👏 결과

---

• 코드에서 하나씩 찍어보면 알겠지만, 반복적으로 방문하는 경우가 많아서, DFS/BFS보다는 시간 면에서 효율적이진 않은 것 같다. (더 효율적으로 짜면 괜찮아질까🤔)