#72 Medium Time O(n^(t/m)) Space O(t/m) Animated

Combination Sum

Find all combinations that sum to target.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Backtracking: choose, explore, unchoose

Build one partial answer at a time and undo each choice so sibling branches start clean.

Approach: DFS (Backtracking)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Build one partial answer at a time and undo each choice so sibling branches start clean.

Common Pitfall

Copy a completed path before appending it to results; later mutations must not alter it.

Description

Find all combinations that sum to target.

Constraints

Time Complexity: O(n^(t/m))
Space Complexity: O(t/m)

Solution — DFS (Backtracking)

TimeO(n^(t/m)) SpaceO(t/m)

Implementation Plan

Translate the invariant into these small, testable moves.

Choose a candidate.
Record the choice.
Explore the next decision.
Undo the choice before trying the next candidate.

def combinationSum(candidates, target):
    res = []
    
    def dfs(i, cur, total):
        if total == target:
            res.append(cur.copy())
            return
        if i >= len(candidates) or total > target:
            return
            
        cur.append(candidates[i])
        dfs(i, cur, total + candidates[i])
        
        cur.pop()
        dfs(i + 1, cur, total)
        
    dfs(0, [], 0)
    return res

Subsets

Permutations

Combination Sum

Steps

Description

Constraints

Tags

Solution — DFS (Backtracking)