[C++] 백준 문제풀이 (Bruteforcing) 14225 부분수열의 합

 

 

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

14225번: 부분수열의 합

 

 

//[C++] 백준 문제풀이 (Bruteforcing)

#include <bits/stdc++.h>


int n;
int arr[21];
bool sums[2000001];

void dfs(int depth, int sum){
    if (depth == n){
        sums[sum] = true;
        return;
    }
    dfs(depth + 1, sum);
    dfs(depth + 1, sum + arr[depth]);
}


int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n;
    for (int i = 0; i < n; ++i){
        std::cin >> arr[i];
    }

    dfs(0, 0);

    int i = 1;
    while(sums[i]){
        ++i;
    }
    std::cout << i << "\n";
    return 0;
}