拼不出的数

【问题描述】

3 个元素的集合 {5, 1,2} 的所有子集的和分别是 0, 1, 2, 3, 5, 6, 7, 8。发现最小的不能由该集合子集拼出 的数字是 4。

现在给你一个 n 个元素的集合，问你最小的不能由该集合子集拼出的数字是多少。

【输入格式】

第一行一个整数 n。

第二行 n 个正整数 ai，表示集合内的元素。

【输出格式】

一行一个整数答案。

【输入样例1】

3
5 1 2

【输出样例1】

4

【数据规模和约定】

对于 30% 的数据，满足 n ≤ 15。

对于 60% 的数据，满足 n ≤ 1000。

对于 100% 的数据，满足 n ≤ 100000, 1 ≤ ai ≤ 10^9。

求思路