백준 1182, 부분수열의 합

개요

문제 링크
실버 2, 브루트포스
부분수열의 합이 S가 되게 하는 경우의 수 구하기

---

접근

1. SSP의 bruteforce 방식을 사용하는 문제. 원소가 음수가 될 수 있고, O(2^n)이 O(nS)보다 작으므로, Knapsack을 사용할 수 없다.
2. 그냥 모든 원소에 100000 더해서 찾아주면 안되냐? 하고 생각할 수 있는데 안된다. 왜냐? 이렇게 하면 S를 찾을 수 없다. N×100000을 더해서 찾아주면 된다고 생각할 수도 있는데, 이건 N개의 원소를 모두 사용할 때의 합이지, N개의 원소 중 일부만 사용하는 경우가 아니다.
3. 즉 원소가 음수인 경우 S를 양수범위 내에서 특정할 수가 없다. 혹시나 해서 map으로도 몇 번 해봤는데 절대 안된다.
4. 나머지는 일반적인 브루트포스를 사용하면 된다. i번째 원소를 추가하는 경우와 추가하지 않는 경우에 대해 재귀적으로 경우를 찾아준다.

---

Pseudo code

void dp(int i,int k) {
    if (i==n) {
        // 끝에 왔을 때 합이 S이면 정답에 1추가
        if (k==s) ans++;
        return;
    }
    dp(i+1,k);
    dp(i+1,k+a[i]);
}

---

Source code

#include <iostream>
using namespace std;

int n,s,ans,a[21];
void dp(int i,int k) {
    if (i==n) {
        if (k==s) ans++;
        return;
    }
    dp(i+1,k);
    dp(i+1,k+a[i]);
}

int main() {
    cin>>n>>s;
    for (int i=0;i<n;i++)
        cin>>a[i];
    dp(0,0);
    if (!s) ans--;
    cout<<ans;
}