백준 1182 - 부분수열의 합

문제

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

1182번: 부분수열의 합

 

풀이

부분수열은 연속적인 부분수열을 의미하는 것이 아니었다. 1, 2, 3, 4의 수열이 있으면 (1, 4), (1, 3, 4) 같이 떨어져 있어도 부분수열이 된다. 이것 때문에 헷갈린 문제다. 

 

배열 각각의 원소를 포함하거나 포함하지 않거나의 2가지 경우로 배열의 모든 인덱스를 탐색하면 된다. 길이가 최대 20이므로 최대 2^20번의 경우가 나온다. 재귀 함수를 이용하면 간단히 풀 수 있다. 

 

코드

#include <iostream>
 
using namespace std;
 
int N, S;
int arr[20];
int num;
 
void f(int arr[], int S, int start, int result)
{
    if (result == S) num++;
    for (int i = start + 1 ; i < N; i++) f(arr, S, i, result + arr[i]);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N >> S;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    for (int i = 0; i < N; i++)
        f(arr, S, i, arr[i]);
 
    cout << num;
    return 0;
}