백준 14225 c++ 부분수열의 합

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

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의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

---

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> getNum;
bool check[2000001];

void Recur(int count, int sum)//재귀적으로 부분수열의 합을 탐색할 함수
{
	check[sum] = true;
	if (count == N)
		return;
	Recur(count + 1, sum);
	Recur(count + 1, sum+getNum[count]);
}


int main()
{
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		getNum.push_back(n);
	}

	Recur(0, 0);

	for (int i = 1; i < 2000000; i++)//처음부터 시작해서 체크안한 가장 작은 수 출력
	{
		if (!check[i])
		{
			cout << i;
			break;
		}
	}
}