[백준]14225 부분 수열의 합

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

출력

 

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

 

 

n번째 숫자를 더했을때, 더하지 않았을때 각각 가지치기하여 방문된 숫자를 표시합니다.

이후, 1부터 체크해서 처음으로 방문하지 않은 숫자를 방문하면 출력하고 끝냅니다.

 

	#include<bits/stdc++.h>
	#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
	#define mset(v) memset(v,0,sizeof(v));
	#define rep(i,a) for(int i=0;i<a;++i)
	#define REP(i,a) for(int i=1;i<=a;++i)

	using namespace std;

	typedef long long ll;
	typedef pair<int, int> pi;
	typedef tuple<int, int, int>ti;
	typedef vector<int> vi;
	typedef vector<vector<int>> vvi;
	int N, M, n[21], v[21], m[2000001], temp;
	void dfs(int k,int sum) {
		if (k >= N)return;
		m[sum+n[k]] = 1;
		dfs(k + 1, sum);
		dfs(k + 1, sum + n[k]);
	}
	int main() {
		FAST;
		int k = 0;
		cin >> N;
		rep(i, N) {
			cin >> n[i];
		}
		dfs(0,0);
		REP(i, 2000001) {
			if (!m[i]) {
				cout << i;
				return 0;
			}
		}
	}