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

 

[적용한 알고리즘]

재귀

 

[아이디어]

다른 부분수열의 합과 동일

 

[생각의 흐름 / 절차] 

만들 수 있는 수들을 index 표시, 

반복문 돌면서 첫번째를 가져오면 될 것 같았다.

 

[교훈]

재귀를 더 연습하자.

직관적으로 와닿을 때까지.

 

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int arr[21];
bool check[20 * 100000 + 1];

void go(int index, int sum){
    if (index == n){
        check[sum] = true;
        return;
    }
    go(index + 1, sum + arr[index]);
    go(index + 1, sum);
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    go(0, 0);

    bool flag = false;
    for (int i = 0; i < 20 * 100000 + 1; i++){
        if (check[i]){
            flag = true;
        }
        else {
            if (flag){
                printf("%d\n", i);
                break;
            }
        }
    }

    return 0;
}