Using Subset Sum algorithm $O(n)$ times to find the subset

Question

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given number. I was asked to use this algorithm (however it is implemented) at most $O(n)$ times to build a subset which satisfies the sum. My solution is given below:

 findSubset(A[1,...,n], sum){
 if(blackBox(A,sum)){
 for i = 1 to n do
 if(blackBox(A - A[i], sum))
 return findSubset(A - A[i],sum);
 endif
 return A; 
 }else
 return [];
 endif
 }

The problem with this solution is that it uses the subSetSum algorithm $O(n^2)$ times. As a hint to optimize the problem to $O(n)$ is that I should not use the loop and appeal only to recursion. Can anyone give a hint for an optimal solution to this problem?

Answer 1

Suppose that $\mathit{sum}$ is the sum of some subset of $A[2],\ldots,A[n]$. Then you can just remove $A[1]$.

Conversely, if $\mathit{sum}$ is not the some of any subset of $A[2],\ldots,A[n]$, then any subset summing to $\mathit{sum}$ must contain $A[1]$. Therefore it consists of $A[1]$ together with a subset of $A[2],\ldots,A[n]$ summing to $\mathit{sum}-A[1]$.

Either way, we have eliminated $A[1]$. We can then go on and eliminate $A[2],\ldots,A[n]$ in sequence.