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

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?

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.