#14225번 부분수열의 합 (C++)

문제 링크 : www.acmicpc.net/problem/14225

14225번: 부분수열의 합

백준 1182번 보다는 약간 업그레이드 된 문제이다. 

하지만 로직은 1182번과 동일하다. 결국 bool문을 통한 계수정렬의 방식으로 접근하면 된다.

 

#include <iostream>
using namespace std;

int arr[21] = {0,}, n = 0;
bool ch[20*100000+1] = {false,};

void dfs(int index, int num){
    if(index>n) return;
    ch[num] = true;
    dfs(index+1, num+arr[index]);
    dfs(index+1, num);
}

int main(void) {
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    dfs(0,0);
    for(int s=0; s<20*100000+1; s++){
        if(!ch[s]){
            cout << s << "\n";
            break;
        }
    }
   return 0;
}