[백준 14225] 부분수열의 합

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 2000002
int arr[22];
bool visited[MAX];
int n,tot;
void suyeol(int cur, int cnt, int sum){
    if(cnt==tot){
        visited[sum]=true;
        maxValue=max(maxValue,sum);
        return;
    }
    
    for(int i=cur; i<n; i++)
        suyeol(i+1,cnt+1,sum+arr[i]);
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> arr[i];
        visited[arr[i]]=true;
    }
    
    for(int i=2; i<=n; i++){
        tot=i;
        suyeol(0,0,0);
    }
 
    for(int i=1; i<=MAX; i++){
        if(!visited[i]){
            cout<< i;
            break;
        }
    }
    
    return 0;
}

부분수열은 길이가 1부터 n까지 가능하므로, 수열의 길이(cnt)가 1부터 n까지일 경우로 나눠서 함수를 돌렸다.

다만, 길이가 1인 경우는 입력 받을 때 처리가 가능하므로 입력받음과 동시에 체크 처리를 해주었고

길이가 2인 경우부터는 suyeol 함수를 돌리면서 부분수열의 합을 체크해줬다.