Search
⌘K
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
2367

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
2367

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
2367result[]

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
2367i = 0result[]start0combo[2,2,2]current_target1

i = 0

0 / 2

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

Complexity

Test Your Knowledge

Login to take the complexity quiz and track your progress

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

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsAnthropic SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift PremiumHello Interview Premium
Legal
Terms and ConditionsPrivacy PolicySecurity
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.