How to know the fewest numbers we should add to get a full array

Question

recently I met a question like this:
Assume you have an int N, and you also have an int[] and each element in this array can only be used once time. And we need to design an algorithm to get 1 to N by adding those numbers and finally return the least numbers we need to add.
For example:

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.

I am thinking of solving this by using DFS. Do you have some better solutions? Thanks!

Answer 1

Here's an explanation for why the solution the OP posted works (the algorithm, briefly, is to traverse the sorted existing elements, keep an accumulating sum of the preceding existing elements and add an element to the array and sum if it does not exist and exceeds the current sum):

The loop tests in order each element that must be formed and sums the preceding elements. It alerts us if there is an element needed that's greater than the current sum. If you think about it, it's really simple! How could we make the element when we've already used all the preceding elements, which is what the sum represents!

In contrast, how do we know that all the intermediate elements will be able to be formed when the sum is larger than the current element? For example, consider 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.