Combination Sum

Patrick Leaton
Published: May 5, 2021, 10:36 p.m.
Problem Description

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: []

Example 4:

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

Example 5:

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

 

Constraints:

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

 

The description was taken from https://leetcode.com/problems/combination-sum/.

Problem Solution

#O(N^T/M+1) Time, O(T/M) Space
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        output = []
        candidates.sort()
        def backtrack(start: int, combo:list, remaining:int) -> None:
            if remaining == 0:
                output.append(list(combo))
                return
            if remaining < 0:
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    return
                combo.append(candidates[i])
                backtrack(i, combo, remaining - candidates[i])
                combo.pop()
        backtrack(0, [], target)
        return output

Problem Explanation

If a problem requires us to return all possible combinations of a given input, typically that is an indication that backtracking is a good approach.

Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function.  This allows us to circulate elements into each valid position so that we can generate each valid combination. 

A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, if not, check if a placement is valid then make the placement.  Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.  

This question is very similar to Path Sum but instead of finding the path sums for a binary tree, we will be doing it on a recursive tree.

We will start by initializing our output array.

        output = []

 

Let's also sort the candidates array for a slight optimization explained later, this step is not required.

        candidates.sort()

Next, we will create our recursive, backtrack function. 

The function will take an index to begin a traversal from and a combo list that contains a Depth First Search path's current combination, as well as a remaining value that indicates what needs to be added to this current combination for it to equal the target value.

        def backtrack(start: int, combo:list, remaining:int) -> None:

 

Let's set a couple of base cases for this function.

First, if the remaining value equals zero, then that means that the candidates within the current combination sum to the target value.  If that is the case, then we will append the combination to the output by taking a deep copy so that the list isn't overwritten later.

We will then return from the function.

            if remaining == 0:
                output.append(list(combo))
                return
 

Also, if the remaining value is less than zero then that means we overshot the target and we should return from this DFS path here since it will not lead to any combination that we will be able to use.

            if remaining < 0:
                return

 

We will now start creating the backtracking logic.

Let's create a loop that will iterate from a given starting number to the last number in the array of candidates.

This is how we will split up the scope of each combination through recursion.  

            for i in range(start, len(candidates)):

 

Next, we will implement the optimization that we can gain by sorting the array of candidates.

If the number in our current iteration is greater than the remaining value, then we should return now because this current DFS path is bad and we will overshoot our target by adding any more values from the candidate array. 

This step isn't required but helps tremendously to prune the recursion tree.

                if candidates[i] > remaining:
                    return

 

Next, we will append the current candidate number from the current iteration to the current combo and recurse the function by incrementing the starting number to the current iterator, passing the combo, and subtracting the remaining value by the current candidate.

                combo.append(candidates[i])
                backtrack(i, combo, remaining - candidates[i])
 
We recurse the function with the current iterator because the description says that we can use the same candidate numbers an unlimited amount of times.  This way, we give candidates multiple tries to get into the output.

 

After we have shot our DFS yoyo down and it has returned back to us, we will pop the last candidate from our combo.  

                combo.pop() 
 
The reason we do this is that we want to allow the function to circulate numbers for each position from the pool of candidates until we have gathered each combination from each valid DFS path.

Now that we have our backtrack function built, we just need to make the initial call by passing zero as the starting number, an initial empty combination, and the target number as the remaining value.

        backtrack(0, [], target)

 

Once we have our output that contains each combination, we will return it and we're done with this question.

        return output

As for the time complexity, for each candidate N, we can calculate T/M where T is the target value and M is the minimum value amount in the candidates since we can just keep adding the smallest value first before any of the others and get the closest combination sum to the target before circulating an additional number.

Similarly, O(T/M) would be the space complexity for the reason mentioned previously.