[BOJ] 백준 14225 부분수열의 합

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

 Input 

3

5 1 2

 

 Output 

4

▶ DFS 이용

원소의 개수는 20개이며 각 원소의 최대값은 100,000이므로

부분 수열 합의 최대값 = 20 × 100,000 = 2,000,000

(연속된 원소로 이루어진 부분 수열 X)

---

#include <iostream>
using namespace std;
#define LM 2000001
bool isOK[LM];
int N, arr[20];
 
void DFS(int idx, int sum){
    if(idx == N){
        isOK[sum] = true;
        return;
    }
 
    // 현재 숫자를 부분수열에 포함하거나 포함하지 않거나
    DFS(idx+1, sum+arr[idx]);
    DFS(idx+1, sum);
}
 
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
 
    DFS(0, 0);
 
    for (int i = 1; i < LM; ++i) {
        if (!isOK[i]) {
            printf("%d", i);
            return 0;
        }
    }
}