[Solution]Problem 76: Combination Sum [Google]

Backtracking, Recursion, Graphs, and Lotta Love

Feb 24, 2023

Hey, it’s your favorite cult leader here 🐱‍👤

On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹

To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!

Help me buy chocolate milk

p.s. you can learn more about the paid plan here.

I hope you’re psyched for this.

This question combines many ideas and concepts that we have covered. Take notes on how we flow between different components of the solution. The transitions will be very useful in your interviews.

Get ready to dance.

Problem

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.

The test cases are generated such 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
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

You can test your solution here

This is a free solution. For more such high-quality posts, subscribe to the newsletter and take your preparation to the next level-

Step 1: Reading the Problem

As soon as we start reading the problem, there should be a bell ringing in our minds. The phrase, ‘list of all unique combinations of candidates’ is a powerful indication that we will be expected to apply some kind of backtracking to the algorithm. That is because, for a given partial configuration, there might be multiple ways to sum to the target. The only way to get them all is through backtracking.

That is one insight, but where can we go from here? Let’s read through the problem carefully, and try to model the interaction between the different components of our solution. At this step, we’re not trying to solve the problem right away. We’re just trying to get a high-level understanding of our prospective system. We’re not solving how the system works, just what it does. The how becomes much easier once we sort this out.

Step 2: Modeling the System

So let’s model this system at a high level. We know that we have a target and some candidates. For any given target, you can reach different states in your program by going picking a different target (7-2 is a different value than 7-3). Once we get to a new state, the process will repeat itself (we can pick new states based on viable candidates), making this process recursive. This shouldn’t come as a huge shocker given the presence of backtracking.

So our system has states and transitions based on a certain operation. Does this seem like a Data Structure that we know? To those not familiar with the graph-spotting framework that I covered here, any time you can model your system as a series of states and transitions between those states, you know that you can solve the question using graphs.

In our case, the target and possible target-candidate combinations all form the states (nodes in our graph). Subtraction of a given candidate from a node forms the transitions (edges) of the system. If this is all too abstract, take a look at the illustration of a very similar system below-

If it helps, you can visualize the system in the question like a Vending Machine, since it has almost identical mechanics. Source

So we have our situation modeled as a graph. What do we do from here? The next step is to simply figure out how we will traverse this graph. Notice that any path that leads from the original target value to 0 will give us a combination that sums to the target. So we run a simple graph traversal algorithm, implement backtracking, and store all the relevant values.

Some of you might be shaking at the thought of this. After all, implementing these concepts are some of the most challenging tasks you can be expected to do. But, remember, one step at a time. Using techniques that I have shown here many times, we will assert our dominance on this question(and our interviewers).

Step 3: Figuring out the correct traversal mechanics

The next challenge is to figure out the correct traversal algorithm. We know that our current system is unweighted (one set of sums is not better than another), so we know that our traversal will either be a BFS or DFS. How can we choose?

Once again, this cult has the answers you need. Months ago, I did a post on how you can choose the correct graph algorithm, based on the different details of the problem. Based on it, we will pick the DFS. Why did you ask? Refer to the following passage-

Visiting the complete graph: For problems where we have to take into account the entire graph (alien dictionary, detecting a cycle etc.), then DFS becomes your best friend. It takes lesser memory.

The main advantage of BFS is in problems involving the shortest path. However, that is not a consideration here. We will traverse all paths anyway. So memory efficiency plays a big role here. Make sure you stress point to your interviewer. Otherwise, I will find your house and make sure this gets drilled into your psyche.

We had to accomplish 3 tasks. One is down.

~~So we run a simple graph traversal algorithm~~, implement backtracking, and store all the relevant values.

Time to wrap this up. I have to go rock climbing. What kinds of activities do you like to do when you’re sick of your screen? Let me know. I’d be interested in hearing about it.

Step 4: Putting all the Pieces together

We have most of the individual components of this puzzle. Time to start integrating them.

Typically these problems can be solved easiest by using a global variable to track all the combinations. This is a great way to track the computations that happen on various stack frames. It is generally helpful to conduct all the recursion in a helper function so that we limit the side effects of the recursion. This gives us the following skeleton-

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def dfs(i, cur, total):
            #something something

         
        dfs(0, [], target)
        return res

So how do we put some meet on the bones? Fortunately, I have already shared my template for writing recursive functions easily over here. The template goes as follows-

Check for termination cases- We have two base cases. Firstly, if we hit the total as being 0 (success). Secondly, we have the failure cases. I’ll leave it to you to figure them out (don’t worry the full code is shared at the end as usual).
Do the processing- Once we have handled the base cases, we get to the next move. We want to facilitate the backtracking leaps. This involves adding the candidate at our given index to our candidate set.
```
            cur.append(candidates[i])
```
Move on to the recursive case- Now we are primed for our recursive move. This step happens twice, since we are exploring multiple paths-
```
            dfs(i, cur, total - candidates[i])
            #reset the side effects here
            dfs(i + 1, cur, total)
 
```
This structure is slightly different from the normal. The reason is that in questions like this we want to consider two cases. 1- We used the value in our current index in our solution. 2- We skipped this index and moved on. The two recursive calls handle both of these cases.
Reset side effects- Fill this out yourself and move on. I don’t want to deprive you of precious practice.

To understand the significance of each step, make sure you read through that article. It will help you understand the theory behind the template and will help you more than just copying this blindly.

If you have smoothly gone through every step, your code should be ready to go now. Let’s look at the final solution.

Step 5: Coding Things Up.

Putting everything together, we get this-

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def dfs(i, cur, total):
            if total == 0:
                res.append(cur.copy())
                return
            if i >= len(candidates) or total < 0:
                return

            cur.append(candidates[i])
            dfs(i, cur, total - candidates[i])
            cur.pop()
            dfs(i + 1, cur, total)

        dfs(0, [], target)
        return res

Consider the elephant eaten.

Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.