[백준] 1182 부분수열의 합 c++

 

문제 링크 https://www.acmicpc.net/problem/1182

KEY

• 부분 수열은 자기 자신을 넣거나, 빼어 만드는 수열로, 2^n가지를 만들 수 있다.
• 따라서 이 문제 역시 자기 자신을 넣고 DFS를 할 것인지, 빼고 DFS를 할 것인지를 모두 고려하면 된다.
• 주의사항은 가령 -1 1 -3 3 수열에 목표값이 0이라고 할 때, 0이 되는 값을 찾았다고 해서 리턴을 하게 되면 (-1,1),(-3,3)만을 찾은 후 리턴하여  (-1,1,-3,3)을 찾지 못하게 된다. 따라서 idx가 n이 될때 리턴하도록 종료조건을 만든다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 21;
int n, s;
int arr[MAX];
int cnt;
void dfs(int idx,int sum) {
 
    if (idx == n) //종료조건
        return;
    if (sum + arr[idx] == s) //합이 target과 같다면 카운트 증가
        cnt++;
 
    dfs(idx + 1, sum + arr[idx]); //더하고 다음 수로 넘어가는 경우
    dfs(idx + 1, sum); //안더하고 다음 수로 넘어가는 경우
}
int main()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    dfs(0,0);
    cout << cnt;
}