[백준] 부분수열의 합

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

1182번: 부분수열의 합

우선 문제부터 간단하게 요약하면, 

 

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열중 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구해야 하는 문제입니다.

 

<Solution>

정수의 개수가 1~20개라고 문제에서 주어졌으므로 dfs알고리즘을 통해 충분히 해결할 수 있을 것을 알 수 있습니다.

 

그래서 고르거나 고르지 않거나로 분기하여 dfs를 진행하고, 만약 합이 S가 되는데 성공하면, 갯수를 세어 주는 방식으로 구현 하면 됩니다. 주의 해야 하는 점은 만약 처음 주어진 값 S가 0이라면, 아무 원소도 고르지 않는 경우가 카운팅 되기 때문에 구해진 갯수에서 1을 빼주어야 함을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>

using namespace std;

int N, S;
int cnt;

int numArray[30];

void dfs(int curIndex, int curSum){
    if(curIndex == N){
        if(curSum == S) cnt++;
        return;
    }
    // 고르는 경우
    dfs(curIndex+1, curSum+numArray[curIndex]);
    // 고르지 않는 경우
    dfs(curIndex+1, curSum);
    return;
}

int main(){
    cin >> N >> S;
    for(int i = 0; i < N; i++){
        cin >> numArray[i];
    }
    dfs(0, 0);

    if(S == 0) cnt--;

    cout << cnt << endl;

    return 0;
}