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

구현해야 할 조건

모든 조합을 생각하면 된다. 중복을 제외하고! DFS를 사용해서 모든 조합을 구할 수 있다. 단, 자주 사용하던 방식이 아니라 조으ㅡ으으으으금 어려웠다. 개인적으로

code

#include<iostream>
#include<cstring>
#include<algorithm>

#define MAX 21
using namespace std;

int n;
int arr[MAX];
bool visited[2000001];

void DFS(int cnt, int sum)
{
	if(cnt == n)
	{
		visited[sum] = true;
		return;
	}
	
	DFS(cnt+1,sum+arr[cnt]);
	
	DFS(cnt+1,sum);
	
}

int main()
{
	
	cin >> n;
	
	for(int i = 0; i < n; i++)
		cin >> arr[i];
		
	memset(visited, false, sizeof(visited));
	
	DFS(0,0);
	
	for(int i = 1; i < 2000001; i++){
		if(!visited[i])
		{
			cout << i;
			break;
		}
			
	}
	
	return 0;
}