[백준 1182] 부분수열의 합

문제 출처: https://www.acmicpc.net/problem/1182

풀이

s를 위한 부분수열(부분집합)을 만들 때, 해당 인덱스값을 더하거나, 더하지않는 경우가 있습니다.

즉 저 두 경우에대해서 s를 만들 수 있는 모든 후보군들이 구해집니다.

주의할 것은 공집합(0)처리입니다. 

s가 0일때, 아래코드를 돌리면 정답+1갯수가 출력되는데, 시작하는 sum이 0부터 시작되므로, 최초의 연산 시, 부분수열을 구하지않았음에도 

재귀함수를 통해(더하지 않았을 때의 함수)언젠가는 최초의 sum=0인값이 s와 동일하다고 인식되어 경우의 수가 하나 추가됩니다. 

그러므로, s=0일 때는 모든 경우를 구하고 한가지경우를 빼준 경우가 답이됩니다.

코드

#include<iostream>
#include<vector>
using namespace std;
int n, s, arr[20], ans;
void dfs(int index,int sum);
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    dfs(0,0);
    if (s == 0)ans--;
    cout << ans << '\n';
}
void dfs(int index,int sum)
{
    if (index == n)
    {
        if (sum == s)
        {
            ans++;
        }
        return;
    }
    //더할때
    dfs(index + 1, sum + arr[index]);
    //더하지않을 때
    dfs(index + 1, sum);
}

결과