백준 1182번 부분수열의 합 - C++

[문제]

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

1182번: 부분수열의 합

[풀이]

백트래킹 문제이다.

 

[코드]

#include <iostream>
using namespace std;

int n,s;
int arr[30];
int cnt;

void func(int cur, int tot){
    if(cur == n)
    {
        if(tot == s) cnt++;
        return;
    }
    func(cur+1, tot);
    func(cur+1, tot+arr[cur]);
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    for(int i=0; i<n; i++)
        cin >> arr[i];
    func(0,0);
    if(s==0) cnt--;
    cout << cnt;
}