如何知道我们应该添加最少的数字以获得完整的数组

Question

最近我遇到了这样一个问题:
假设你有一个int N,你也有一个int [],这个数组中的每个元素只能使用一次.我们需要设计一个算法,通过添加这些数字来获得1到N,最后返回我们需要添加的最少数字.
例如:

N = 6, array is [1,3]
1 : we already have.
2 : we need to add it to the array.
3 : we can get it by doing 1 + 2.
4: 1 + 3.
5 : 2 + 3.
6 : 1 + 2 + 3.
So we just need to add 2 to our array and finally we return 1.

我正在考虑使用DFS解决这个问题.你有更好的解决方案吗？谢谢!

Answer 1

这是OP发布的解决方案的工作原理的解释（简单地说，该算法是遍历已排序的现有元素，保留前面现有元素的累加和，并将一个元素添加到数组中，如果不存在且超过该元素，则将其求和当前总和）：

该循环按顺序测试必须形成的每个元素并对前面的元素求和。如果需要的元素大于当前总和，它会提醒我们。如果你仔细想想，其实很简单！当我们已经使用了所有前面的元素（这就是总和所代表的内容）时，我们如何才能创建该元素！

相比之下，当总和大于当前元素时，我们如何知道所有中间元素都能形成？例如，考虑n = 7, a = {}：

The function adds {1,2,4...} 
So we are up to 4 and we know 1,2,3,4 are covered,
each can be formed from equal or lower numbers in the array.

At any point, m, in the traversal, we know for sure that 
X0 + X1 ... + Xm make the largest number we can make, call it Y.
But we also know that we can make 1,2,3...Xm

Therefore, we can make Y-1, Y-2, Y-3...Y-Xm

(In this example: Xm = 4; Y = 1+2+4 = 7; Y-1 = 6; Y-2 = 5)

Q.E.D.