algorithm - 如何找到输入序列无法表示的最小数量

下面是一个面试问题：
输入：
整数n；不同的正整数a1，a2…一个；
输出：
最小正整数m，它不能以m＝x1*a1+x2*a2+…xn*an表示，其中x= {0,1}。

最佳答案

天真的解决方案：

public static void calcAllSums(int[] arr, int sum, int curIndex, Hashtable<Integer,Boolean> sums){
    if (curIndex == arr.length) return;
    int sum1 = sum+arr[curIndex];
    int sum2 = sum;
    sums.put(sum1, true);
    sums.put(sum2, true);
    calcAllSums(arr, sum1, curIndex+1, sums);
    calcAllSums(arr, sum2, curIndex+1, sums);
}
public static void main(String[] args){
    int[] arr = {1,3,5};
    Hashtable<Integer,Boolean> sums = new Hashtable<Integer,Boolean>();
    calcAllSums(arr, 0, 0, sums);
    int i=0;
    while (sums.containsKey(i)) i++;
    System.out.println(i);
}

我计算了所有可能的和，然后迭代，直到找到一个不在列表中的整数

关于algorithm - 如何找到输入序列无法表示的最小数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7801980/