# 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,\ldots,A[n]$$. Then you can just remove $$A$$.
Conversely, if $$\mathit{sum}$$ is not the some of any subset of $$A,\ldots,A[n]$$, then any subset summing to $$\mathit{sum}$$ must contain $$A$$. Therefore it consists of $$A$$ together with a subset of $$A,\ldots,A[n]$$ summing to $$\mathit{sum}-A$$.
Either way, we have eliminated $$A$$. We can then go on and eliminate $$A,\ldots,A[n]$$ in sequence.