부분 수열의 합으로 만들 수 없는 수

시간 제한2초메모리 제한512 MB

요약

N ≤ 20인 수열이 주어질 때, 어떤 비어 있지 않은 부분수열의 합으로도 만들 수 없는 가장 작은 자연수를 구한다.

난이도: 보통10점 중 5점
유형: 백트래킹, 완전 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

수열 $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 \le N \le 20$ )

둘째 줄에 $S$ 의 원소 $N$ 개가 공백으로 구분되어 주어진다. 각 원소는 100,000 이하의 자연수이다.

출력

첫째 줄에 $S$ 의 부분 수열의 합으로 만들 수 없는 가장 작은 자연수를 출력한다.

예제3

예제 1
입력
```
3
5 1 2
```
예상 출력
```
4
```
예제 2
입력
```
3
2 1 4
```
예상 출력
```
8
```
예제 3
입력
```
4
2 1 2 7
```
예상 출력
```
6
```