Given an array consisting of only positive integers and a target sum.
Generate all the combinations from the array that sum up to the given target sum.
a = [2, 4, 6, 8]
target = 8
ans = [(2, 6), (2, 2, 2, 2), (2, 2, 4), (8,), (4, 4)]
If we observe, we can formulate the following pattern for the problem.
At any point, either a number has to included in the patter or not included.
If it's included, it'll be subtracted from the required sum, otherwise required sum will remain the same and we'll move forward.
The above approach can be consolidated in the following algorithm:
1. Start with the first element of the array.
2. For all index i.
3. If we included the element: then solve recursively for (sum - a[index], index)
4. If we decide not to include this element, then solve recursively for (sum, index)