[Brute Force - 비트마스크] 부분수열의 합

예제 입력 1

3

5 1 2

예제 출력 1

4

예제 입력 2

3

2 1 4

예제 출력 2

8

예제 입력 3

4

2 1 2 7

예제 출력 3

6

 

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

 

#include <stdio.h>
#define MAX_SIZE (21)
#define MAX_NUMBER (20*100000+1)

int N;
int numbers[MAX_SIZE];
bool canMake[MAX_NUMBER];

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &numbers[i]);
	}

	for (int i = 0; i < (1 << N); i++)
	{
		int sum = 0;

		for (int j = 0; j < N; j++)
		{
			if(i & (1 << j))
			{
				sum += numbers[j];
			}
		}

		canMake[sum] = true;
	}

	for (int i = 1; i <= MAX_NUMBER; i++)
	{
		if (!canMake[i])
		{
			printf("%d\n", i);
			break;
		}
	}

	return 0;
}