algorithm - 如何找到输入序列不能表示的最小数

Question

这是一道面试题:输入:整数N；不同的正整数a1,a2 ... aN;

输出:最小正整数 m，不能以 m = x1*a1+x2*a2+...xN*aN 的形式表示，其中 xi={0,1}。

Answer 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);
}

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