MediumBlind75ArrayBacktracking

Combination Sum

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. The same number may be chosen from candidates an unlimited number of times.

Examples

Input
candidates = [2,3,6,7], target = 7
Output
[[2,2,3],[7]]

2+2+3=7 and 7=7.

Input
candidates = [2,3,5], target = 8
Output
[[2,2,2,2],[2,3,3],[3,5]]

Multiple combinations sum to 8.

Constraints

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

Approaches

Generate all possible combinations and check their sum.

CodeT: O(n^target) | S: O(target)
def combination_sum(candidates, target):
    result = []
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])
            current.pop()
    backtrack(0, [], target)
    return result

Use backtracking with pruning when remaining becomes negative.

CodeT: O(n^target) | S: O(target)
def combination_sum(candidates, target):
    result = []
    candidates.sort()
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])
            current.pop()
    backtrack(0, [], target)
    return result

Same backtracking with sorting for early termination.

Diagram

candidates = [2,3,6,7], target = 7 Sort: [2,3,6,7] 2->2->2->1(no) backtrack 2->2->3=7 ✓ -> [2,2,3] 2->3->2=7 ✓ (same as above, avoided by i>=start) 7=7 ✓ -> [7]
CodeT: O(n^target) | S: O(target)
def combination_sum(candidates, target):
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])
            path.pop()
    candidates.sort()
    backtrack(0, [], target)
    return result

Complexity Comparison

Brute Force - All Combinations
T: O(n^target)S: O(target)

Generate all possible combinations and check their sum.

Backtracking with Pruning
T: O(n^target)S: O(target)

Use backtracking with pruning when remaining becomes negative.

Optimized Backtracking
T: O(n^target)S: O(target)

Same backtracking with sorting for early termination.

Common Mistakes

Not sorting candidates for early termination

Using the wrong starting index in recursion

Not handling the case where a single candidate equals the target

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems