[Java] Number of subsequences that sum up to target with dynamic programming

We have seen a graph approach to the problem of finding the number of subsequences that sum up to a given target, however that approach was inefficient since we kept evaluating the same unique nodes multiple times.

With dynamic programming, we can reduce complexity by caching partial results.

We approach the problem from a similar perspective, but perform a DFS instead of BFS and cache the ways we calculated a partial sum from a given element in the array.

For each element in the array, all previous subsequences have been investigated, therefore we can consider only the contribution we would add to those partial sums.

Space and time complexity becomes O(NM) where N is size of input array and M is target value.

You can check my implementation of howManySubsequencesSumUpToTargetDP on my Gist along with some tests in HowManySubsequencesSumUpToTargetDPJTests.