14225번

14225번 - 부분수열의 합

단순한 조합 문제였다. 수열의 갯수도 최대 20개 이므로 시간복잡도는 O(2^20)이 된다. 따라서 완전탐색으로 충분히 해결할 수 있다.

<정답 코드>

#include<iostream>
 
using namespace std;
#define MAX 2000001
int N;
int S[20];
int num[MAX];
void go(int k,int sum)
{
    if (k == N)
    {
        num[sum] = 1;
        return;
    }
 
    go(k + 1, sum + S[k]);
    go(k + 1, sum);
 
}
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> S[i];
 
    go(0,0);
 
    for (int i = 1; i <= MAX; i++)
    {
        if (num[i] == 0) 
        {
            cout << i << endl;
            break;
        }
    }
 
 
    return 0;
}