(c++)백준 14225번: 부분수열의 합

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

14225번: 부분수열의 합

[풀이]

원소가 1개 이상인 모든 조합에 대해 원소값들의 합을 구하고, 만들 수 있는 자연수 i에 대해 canMake[i]를 true로 저장한다. 마지막에 1부터 시작하여 만들 수 없는 자연수가 나올 때까지 for문을 돌린다.

 

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

int N;//수열 S의 크기
vector<int>S(20);//주어진 수열
bool check[20];
vector<int>Set;
bool canMake[20 * 100000 + 1];//부분 수열의 합으로 나올 수 있는 자연수 체크

void Calc() {
	int L = Set.size();
	int sum = 0;
	for (int i = 0; i < L; i++) {
		sum += Set[i];
	}
	canMake[sum] = true;
}

//원소가 1개 이상인 모든 조합 구하기
void getSum(int idx, int cnt) {
	if (cnt >= 1)
		Calc();
	for (int i = idx; i < N; i++) {
		if (check[i] == true)
			continue;
		check[i] = true;
		Set.push_back(S[i]);
		getSum(i, cnt + 1);
		check[i] = false;
		Set.pop_back();
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
	}
	getSum(0, 0);
	for (int i = 1; ; i++) {
		if (canMake[i] == false) {
			cout << i << '\n';
			break;
		}
	}
}

int main() {
	solution();
	return 0;
}