题意:

给定一个集合,求不能由该集合子集拼出的最小数。

样例:

{2,5,1}

1,2,3均可以拼出,4不能拼出,故答案是4.

思路:

先把集合元素从小到大排序,首先,假设第1个数必须是1,否则答案就是1.

归纳法假证

x=1时可以拼出1.(第1项满足)

对于任意x(x>=2),令s=Σ a(i), i∈[1,x-1] ,如果1~a(i)-1均能拼出(即s>=a(i)-1),加一个a(i)可以拼出1~s+a(i).

因此:方法就是找第一个a(x),满足s=Σ a(i), i∈[1,x-1],满足s<=a(i)-2.这时s+1就是答案。

这个思路类似于多重背包的二进制拆分