백준 14225번 부분수열의 합 C++

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

 

수열의 크기는 최대 20이고, 수열을 이루는 각 수가 최대 100000이기 때문에 나올 수 있는 최대의 수는 2000000이다.

2000000개의 크기를 갖는 배열을 만들어서 재귀함수를 통해 나온 수들의 합을 저장하고, 배열을 1부터 탐색하면서 만약 저장되지 않은 수를 찾는다면 탐색을 멈추고 탐색이 멈춘 부분을 출력하는 방식으로 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

vector<int> v;
bool ans[2000001] = { false };

void solve(int index, int val) {
	for (int i = index; i < v.size(); i++) {
		ans[v[i] + val] = true;
		solve(i + 1, val + v[i]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, input;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		v.push_back(input);
	}
	solve(0, 0);
	int key = 1;
	for (int i = 1; i < 2000001; i++) {
		if (ans[i] == false) {
			key = i;
			break;
		}
	}
	cout << key;
};