Limited Time Offer:Up to 0% off Hello Interview Premium

⌘K

Tutor

Backtracking

Combination Sum

medium

DESCRIPTION (inspired by Leetcode.com)

Given an array of distinct integers candidates and a target integer target, generate all unique combinations of candidates which sum to target. The combinations may be returned in any order, and the same number may be chosen from candidates an unlimited number of times.

Constraints:

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

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.

Solution

Visualization

Try these examples:


def combinationSum(candidates, target):
    def backtrack(start, combo, current_target):
        if current_target == 0:
            result.append(list(combo))
            return
        for i in range(start, len(candidates)):
            curr = candidates[i]
            if candidates[i] > current_target:
                return
            combo.append(curr)
            backtrack(i, combo, current_target - curr)
            combo.pop()
        return
    
    candidates.sort()
    result = []
    backtrack(0, [], target)
    return result

combination sum

0 / 56

Explanation

This solution uses backtracking to find all the combinations of numbers that sum up to the target. The backtracking function is a recursive function that uses depth-first search to explore all possible combinations of candidates that sum up to the target. Each call to backtracking takes in parameters start, combo, and current_target. The start parameter is the index of the current candidate, combo is the current combination of numbers, and the current_target parameter is the target we are trying to hit (equal to target - the sum of combo).

The first step is to sort candidates, which makes it easy to tell when the current search combination exceeds the target, and can be pruned.

Visualization


def combinationSum(candidates, target):
    def backtrack(start, combo, current_target):
        if current_target == 0:
            result.append(list(combo))
            return
        for i in range(start, len(candidates)):
            curr = candidates[i]
            if candidates[i] > current_target:
                return
            combo.append(curr)
            backtrack(i, combo, current_target - curr)
            combo.pop()
        return
    
    candidates.sort()
    result = []
    backtrack(0, [], target)
    return result

combination sum

0 / 1

Next, we kick off the search. Each call to the backtracking function first checks if the current_target is equal to 0. If so, that means the current value for combo is a valid solution, so we add it to the result. If not, the function iterates through the candidates starting from the start index. For each candidate, we add it to the current combination and recursively call the backtracking function with the updated current_target. Since we can use the same candidate multiple times, we pass the start index as the current index to the next call.

Visualization


def combinationSum(candidates, target):
    def backtrack(start, combo, current_target):
        if current_target == 0:
            result.append(list(combo))
            return
        for i in range(start, len(candidates)):
            curr = candidates[i]
            if candidates[i] > current_target:
                return
            combo.append(curr)
            backtrack(i, combo, current_target - curr)
            combo.pop()
        return
    
    candidates.sort()
    result = []
    backtrack(0, [], target)
    return result

sort candidates

0 / 10

Recursively exploring all combinations

If at any point the current_target becomes less than 0, we know that the current combo is not a valid solution, so we backtrack to the previous call.

For the backtracking step, we remove the last number from the current combination and try the next candidate. This process continues until we have tried all the candidates.

Visualization


def combinationSum(candidates, target):
    def backtrack(start, combo, current_target):
        if current_target == 0:
            result.append(list(combo))
            return
        for i in range(start, len(candidates)):
            curr = candidates[i]
            if candidates[i] > current_target:
                return
            combo.append(curr)
            backtrack(i, combo, current_target - curr)
            combo.pop()
        return
    
    candidates.sort()
    result = []
    backtrack(0, [], target)
    return result


def backtrack(start, combo, current_target):
    if current_target == 0:
        result.append(list(combo))
        return
    for i in range(start, len(candidates)):
        curr = candidates[i]
        if candidates[i] > current_target:
            return
        combo.append(curr)
        backtrack(i, combo, current_target - curr)
        combo.pop()
    return


def backtrack(start, combo, current_target):
    if current_target == 0:
        result.append(list(combo))
        return
    for i in range(start, len(candidates)):
        curr = candidates[i]
        if candidates[i] > current_target:
            return
        combo.append(curr)
        backtrack(i, combo, current_target - curr)
        combo.pop()
    return


def backtrack(start, combo, current_target):
    if current_target == 0:
        result.append(list(combo))
        return
    for i in range(start, len(candidates)):
        curr = candidates[i]
        if candidates[i] > current_target:
            return
        combo.append(curr)
        backtrack(i, combo, current_target - curr)
        combo.pop()
    return


def backtrack(start, combo, current_target):
    if current_target == 0:
        result.append(list(combo))
        return
    for i in range(start, len(candidates)):
        curr = candidates[i]
        if candidates[i] > current_target:
            return
        combo.append(curr)
        backtrack(i, combo, current_target - curr)
        combo.pop()
    return

i = 0

0 / 2

Backtracking to the previous call. Notice how we `pop` from `combo` when we backtrack.

Complexity

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n^(T/m)) Let n be the number of candidates, T be the target value, and m be the smallest candidate. In the worst case, the recursion tree branches up to n ways at each level, and the maximum depth is T/m (achieved by repeatedly picking the smallest candidate). This gives an upper bound of O(n^(T/m)) nodes in the recursion tree. The sorting step takes O(n log n), which is dominated by the backtracking.

Space Complexity: O(T/m) The recursion goes at most T/m levels deep (each level subtracts at least m from the remaining target), so the call stack and the current combination together use O(T/m) space. We don't count the output list itself.

Mark as read

Next: Palindrome Partitioning

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations

Guided Practice

Recent interview questions

Learn More

Reading Progress

On This Page

Solution

Explanation

Complexity

Backtracking

Combination Sum

DESCRIPTION (inspired by Leetcode.com)

Solution

Explanation

Complexity

Test Your Knowledge

Complexity Analysis

Comments

Questions

Learn

Links

Legal

Contact