Grokking the Coding Interview: Patterns for Coding Questions

0% completed

Solution: Combination Sum

On This Page

Problem Statement

Why this is a Backtracking problem

Solution

Code

Time Complexity

Space Complexity

Problem Statement

Given an array of distinct positive 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.

Example 1:

Input: candidates = [2, 3, 6, 7], target = 7  
Output: [[2, 2, 3], [7]]  
Explanation: The elements in these two combinations sum up to 7.

Example 2:

Input: candidates = [2, 4, 6, 8], target = 10  
Output: [[2,2,2,2,2], [2,2,2,4], [2,2,6], [2,4,4], [2,8], [4,6]]    
Explanation: The elements in these six combinations sum up to 10.

Constraints:

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

About the output order. Build combinations by scanning the candidates in the given order, allowing repeats of the current candidate before moving right, the order the examples show: for [2,3,6,7] and target 7, the answer is [[2,2,3],[7]]. The judge compares your list against this exact order, so a correct set of combinations arranged differently, such as [[7],[2,2,3]], is currently marked wrong.

Why this is a Backtracking problem

What the question says	The signal it matches
"return a list of all unique combinations"	you need every valid answer
"where the chosen numbers sum to target"	a partial answer can be ruled out early once the total passes the target
"The same number may be chosen from candidates an unlimited number of times"	each step is a choice, and the same choice may repeat

This is the choose numbers towards a target variant: add a candidate, and stop when the total passes the target.

The closest alternative. Generate every combination of the candidates and keep those that sum to the target. That is the Subsets pattern, and here it does far more work than needed.

The pruning is what separates the two, and it is one comparison. Because the candidates are positive, a running total that already passes the target can never come back, so that whole branch is abandoned at once. The introduction defines backtracking as exactly this: the Subsets walk with a rule that abandons a branch as soon as it cannot succeed. Note the unlimited reuse, which means a chosen number stays available at the same position rather than being consumed.

Solution

This problem is quite similar to the example discussed in the previous lesson (placing apple, orange, and mango trees).

We can follow the brute-force approach to incrementally build the solution.

If, at any time, we find out that the current solution can't lead to a valid combination, we will abandon it and backtrack to try the remaining solutions.

Let's try this approach on the following input: Candidates: [3, 4, 5], Target: 9

candidates = [3, 4, 5] and target = 9. Start with an empty combination, so the remaining target is 9.

1 of 9

Code

The basic idea is to start with an empty combination and iterate through the candidates array, adding each candidate to the current combination and recursively calling the function with the updated combination and the remaining target. If the target becomes 0, we add the current combination to the result list. If the target becomes negative, we backtrack and remove the last added candidate from the combination.

The function combinationSum takes in two parameters, an array of distinct integers candidates and a target integer target, and returns a list of all unique combinations of candidates where the chosen numbers sum to target. The function starts by defining the function backtrack(candidates, start, target, comb, res). This function takes five parameters, candidates, start, target, comb, and res:

candidates is the array containing candidate elements.
start is the starting index of the candidates array.
target is the remaining target.
comb is the current combination.
res is the final result list.

The backtrack function uses recursion to find the combinations. The base case for the recursion is if the target is 0. When the target is 0, that means we have found a valid combination and we append a copy of the current combination to the result list. It then iterates through the candidates array starting from the given index. If the current candidate is greater than the remaining target, it skips the current candidate and move on to the next. If the current candidate is less than the remaining target, it adds the current candidate to the current combination, recursively calls the function with the updated combination and remaining target, and then backtracks by removing the last added candidate from the combination.

Python3

. . . .

Time Complexity

This algorithm has a time complexity of $O(N^{{T/M}+1})$ , where $N$ is the total number of elements in the candidates array, $T$ is the target value, and $M$ is the smallest value among the candidates. This is because the execution of the backtracking is similar to a DFS traversal of an n-ary tree. So, the time complexity would be the same as the number of nodes in the n-ary tree. This can be seen in the above diagram.

Each node can call the backtrack function a maximum of $N$ times, i.e., the total number of candidates. The maximal depth of the n-ary tree would be $T/M$ , where we keep on adding the smallest element to the combination. As we know, the maximal number of nodes in N-ary tree of $T/M$ height would be $N^{{T/M}+1}$ , hence the time complexity is $O(N^{{T/M}+1})$ .

Space Complexity

Ignoring the space needed for the output array, the space complexity will be $O(T/M)$ because at any time, we can pile up to $T/M$ recursive calls of the backtrack function; this will happen when we keep on adding the smallest element to the combination. As a result, the space overhead of the recursion is $O(T/M)$ .

Mark as Completed

focusssspro

· 4 months ago

You have test case:


[2,3,5]
0

But in constrains it is said: 1 <= target <= 40

Show 1 reply

makarand.h

· 2 years ago

Show 1 reply

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def combinationSum(self, candidates, target):
  
    def backtrack(result, index, path, add):
      if add > target:
        return 
        
      if add == target:
        result.append(path[:])
         
      for i in range(index, len(candidates)):

        path.append(candidates[i])
        add += candidates[i]
        backtrack(result, i, path, add)
        add -= candidates[i]
        path.pop()

    result = []
    backtrack(result, 0, [], 0)
     
    return result

Show 1 reply

Reading Progress

Vote for new content

On This Page

Problem Statement

Why this is a Backtracking problem

Solution

Code

Time Complexity

Space Complexity