[백준/백트래킹/C++] 1182번 부분수열의 합

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

1182번: 부분수열의 합

문제 해결 방법

k를 차례로 증가시키면서 k번째 원소를 합하거나 합하지 않는 두가지 경우로 백트래킹을 한다

#include <bits/stdc++.h>

using namespace std;

int n, s;
int arr[21];
int result = 0;

void backtrack(int k, int tot){
    if(k == n){
        if(tot == s) result++;
        return;
    }
    backtrack(k+1, tot); // k번째 원소를 더하지 않는 경우
    backtrack(k+1, tot+arr[k]); // k번째 원소를 더하는 경우
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    backtrack(0, 0);

    if(s == 0) result--;
    cout << result;


    return 0;
}

 

참고

https://www.youtube.com/watch?v=Enz2csssTCs&t=3s