[Java] Number of subsequences that sum up to target value

Given an unsorted array of positive integers without duplicates and a target value, find how many subsequences of the array sum up to the given target.

Example: [10,6,2,4] target = 100, result is none

[10,6,2,4] target = 16, result is 2: (10,6,) and (10,2,4,)

We can see this problem as a graph search where each node represents the partial sum generated by the elements chosen in the subsequence create until that point. This is very similar to counting how many ways we can reach a target, but in this instance we are only allowed to pick each item once.

For each value in the array, we have a choice to either include it in a subsequence or not, this choice is repeated for each intermediate node in our graph until we deplete the elements in the input array.

In our example that would be (each node has two children in the next level and elements in parentheses indicate nodes that we did NOT enqueue because they were either the target or bigger than the target):

0

0 10

0 6 10 (16)

0 2 6 8 10 12 (16) (18)

[0 4 2 6 6 10 8 12 10 14 12 (16) (16) (20) (18) (22)]

Before enqueuing a node, we verify whether there are more elements in the array after it, otherwise it makes no sense enqueuing it as we won't get there to process it. Therefore the last level in square brackets is NOT added to the queue.

Everytime we encounter a node whose sum is the target, we track it. Since we have no duplicates and process elements in order, we won't ever add the same node (same subsequence) twice. HOWEVER we keep adding the exact same node over and over to the queue as we need it to calculate the longer subsequences starting from there.

To determine when to start considering the next element from our input, we keep enqueueing a marker value (0) and each time we encounter it, we move a pointer to the next element in the input array. When this pointer exceeds the array bounds, we terminate the search.

Additionally, to reflect the "pick current element or not" choice, we always enqueue the current node without summing it to the current element as well.

For each element in our array we add 2^level elements in the queue at most, and the number of levels is at most is the length of our array, therefore we have a runtime of O(2^N) and space is also O(2^N) which is the case where we have added the last level to our queue. 

This is a clear case where dynamic programming helps reducing the complexity by avoiding the repeated processing of the exact same node multiple times.

You can check my implementation of howManySubsequencesSumUpToTarget on my Gist along with some tests in HowManySubsequencesSumUpToTargetJTests.