1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.