[Java] Subset of sum K

Given an array of positive integers, with possible duplicates, find if a subset exists whose sum is a given target.

Example:

1,2,3 target 3 result = {1,2} or {3}

1,2,3 target 5 result = {}

This is clearly a dynamic programming problem, however I think the approach of using a matrix as cache makes it a bit harder to backtrack to a valid solution.

The idea is to start with the given target, then from all available elements in a certain range (initially 0 to array.length - 1), subtract each of them and recurse on the remaining ones. If any call reaches target 0, we have found a solution.

If we had only to determine whether such subset exists, this would be enough, however I still think a matrix might be using more memory in practice than needed as we would create it with size [target + 1][number of elements] for top down recursion at least.

Not all values between 0 and target (inclusive) might be explored though, wasting some space on average, worst case space complexity is still O(NM).

While trying the exercise, I set as values in the matrix the new target that could be reached by choosing the element at the given index starting at the given target which made backtracking a bit strange when recreating the path taken from last to first operation, it did not appear clear to me.

I therefore decided to split my caching from my backtracking and use a set of pairs (target,index) to track which branches of the recursion I had already visited, and a stack of elements to track the current path to the solution.

This means we can find a solution in O(NM) time and space, and recreate it in O(N) time and space. Where N = target (range of values 0..target) and M = number of elements in the array.

Since we are doing DFS, we keep adding elements to the stack while go deeper, if we ever reach 0, it means there is a subset that has sum K. The elements that compose that subset are in the stack.

If we do not reach 0 and and therefore returning unsuccessfully from a call, we can pop the top element from the stack as we know it cannot be part of the solution.

At the end, we either have reached 0 or not.

This approach produces ONE possible subset.

You can check my implementation of subsetOfSumK on my Gist along with some tests in SubsetOfSumKJTests.