Combination Sum🦂

Question

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• All elements of candidates are distinct.
• 1 <= target <= 500

Solution

So if you look at the question we have to generate every possible subsequence which can be generated from the given array and not just every possible subsequence, as the question states that any digit can be used multiple times as well. So if I have been given an array {1} and a target 10 then there will be a combination sum {1,1,1,1,1,1,1,1,1,1} even if the array has only 1 element in it but I'm allowed to use the same number as many times as I want.

So it's not just all the subsequence that I have to check I also have to check the sequence which can be generated by using the same digit multiple times.

And one important thing, if you don’t know how to generate all the possible subsequences for an array, I have already written an article about it, so it won’t make any sense copying and pasting those words again here. Click here 📌to read that article first in order to understand how to generate all the possible sub-sequences for an array.

It's really important you know how to generate all the possible subsequences for an array, so don’t read any further until you finish up that article first.

So, assuming you already know how to generate every possible subsequence for an array. We still have one problem this question states that any single digit can be used multiple times.

So how the hell are we going to do that?

Well, it's actually very simple if you have read that other article which I pinned above. So on each element, we have two choices to either pick the current index item or ignore it and once we make either of the choices we then move forward in the array but this time on the left recursion call we won’t be incrementing our index by 1 i.e. we will be adding the same index or digit again and again until our target value is either 0 or less than 0. The target value will be decreasing on each recursion call because we will be subtracting it by the index which will be on that recursion call. This way if our target value is each to 0 that means we have found a particular sequence whose sum is equal to the target.

I know it sounds weird reading all these words, but once you will see the code and more importantly recursion tree you will understand what I mean by all this.

Here is the recursion tree, take some time here and try to understand the words which I wrote above with this recursion tree and see what's actually happing.

Click here to see the image in high quality

Code

Take any array example and try to draw the recursion tree to understand the flow and mechanism of the code better.

If you learned anything from this article please press that follow button

if (!already)🚗