How do you solve Combination Sum?

Use a recursive DFS function with parameters: current index, current path, and current total sum. When total equals target, add a copy of the path to results. If total exceeds target or index is out of bounds, backtrack. The recursion explores two branches at each step: include the candidate and recurse with the same index, or skip it and recurse with the next index. This ensures all valid combinations are found efficiently.

Combination Sum

Q: What is the time complexity of Combination Sum?

O(2^t). The time complexity is exponential in the target value t, as the recursion explores all possible combinations of candidates that sum up to target, which can be exponential in the worst case.

Q: What pattern does Combination Sum use?

The Pattern: Backtracking (State Restoration) The Heuristic: For 'find all combinations/permutations' problems, use a 'choose, explore, un-choose' backtracking template. The critical step is to 'un-choose' (e.g., path.pop()) after the recursive call returns, which cleans up the state for the next branch of the search.

Medium Backtracking

Problem

Given an array of distinct integers candidates and an 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.

1 ≤ candidates.length ≤ 30
2 ≤ candidates[i] ≤ 40
1 ≤ target ≤ 40

Example

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

Output: [[2,2,3],[7]]

Starting with an empty path and total 0, the algorithm explores including 2 repeatedly: [2], total=2; then [2,2], total=4; then [2,2,3], total=7, which matches the target and is added to results. It backtracks by removing the last 3 and tries other candidates. Another path is choosing 7 directly, which also sums to 7. The recursion systematically explores all combinations by choosing or skipping candidates, ensuring no duplicates and covering all valid sums.

Approach

Straightforward Solution

A brute-force method would generate all possible combinations of all lengths and check sums, which is combinatorially explosive and inefficient.

Core Observation

The problem requires enumerating all unique combinations summing to a target, with unlimited reuse of elements. This naturally forms a decision tree where each candidate can be chosen multiple times or skipped, making backtracking the ideal approach.

Path to Optimal

Preview

The key insight is to structure the search as a depth-first traversal of a decision tree, where at each step the algorithm decides to include the current candidate (and recurse with the same index) or skip it (recurse with the next index)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS function with parameters: current index, current path, and current total sum. When total equals target, add a copy of the path to results…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(2^t)

The time complexity is exponential in the target value t, as the recursion explores all possible combinations of candidates that sum up to target, which can be exponential in the worst case.

Space

O(t)

The recursion stack and current path can grow up to length t in the worst case (e.g., repeatedly choosing the smallest candidate), so auxiliary space is O(t). The output space is not counted here.

Pattern Spotlight

Backtracking (State Restoration)

For 'find all combinations/permutations' problems, use a 'choose, explore, un-choose' backtracking template. The critical step is to 'un-choose' (e.g., path.pop()) after the recursive call returns, which cleans up the state for the next branch of the search.

Solution

Python

1class Solution:
  def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
      res = []
4
      def dfs(i, cur, total):
          if total == target:
              res.append(cur.copy())
              return
          if i >= len(candidates) or total > target:
              return
11
          cur.append(candidates[i])
          dfs(i, cur, total + candidates[i])
          
          cur.pop()
          dfs(i + 1, cur, total)
17
      dfs(0, [], 0)
      return res

Step-by-Step Solution

Initialize Result Container and Start Recursive Search

3res = []
18dfs(0, [], 0)
19return res

Objective

To prepare the container for storing valid combinations and initiate the recursive backtracking process from the first candidate.

Key Insight

The result list accumulates all valid combinations found during recursion. Starting the DFS from index 0 with an empty path and total 0 represents the root of the decision tree, from which all combinations are explored systematically.

Interview Quick-Check

Core Logic

The recursion starts at index 0 with an empty path and total 0, representing the initial state before any candidates are chosen.

State & Boundaries

The result list must be initialized before recursion to collect all valid combinations.

Define DFS Helper and Terminate Upon Reaching Target or Invalid State

To define the base cases that stop recursion when a valid combination is found or when the current path cannot lead to a valid solution.

Explore Including Current Candidate and Backtrack

To explore the decision branch where the current candidate is included, updating the path and total accordingly.

Explore Skipping Current Candidate to Move Forward

To explore the decision branch where the current candidate is skipped, advancing the index to consider the next candidate.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 15 Critical

cur.pop()

Remove the last candidate from the path to backtrack.

This 'un-choose' step restores the path state, enabling exploration of alternative branches without contamination from previous choices.

Line 7 Critical

res.append(cur.copy())

Add a copy of the current path to the results.

Copying the path is essential because the path list is mutable and will be modified during backtracking; without copying, all results would reference the same list.

Line 13 Critical

dfs(i, cur, total + candidates[i])

Recursively explore further combinations including the current candidate.

Recursing with the same index allows unlimited reuse of the candidate, essential for covering all valid combinations.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

What enables the algorithm to reuse the same candidate multiple times in the combinations?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Combination Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Combination Sum drill

or drill a free problem

1	`class Solution:`
2	`def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:`
3	`res = []`
4
5	`def dfs(i, cur, total):`
6	`if total == target:`
7	`res.append(cur.copy())`
8	`return`
9	`if i >= len(candidates) or total > target:`
10	`return`
11
12	`cur.append(candidates[i])`
13	`dfs(i, cur, total + candidates[i])`
14
15	`cur.pop()`
16	`dfs(i + 1, cur, total)`
17
18	`dfs(0, [], 0)`
19	`return res`

3	`res = []`
18	`dfs(0, [], 0)`
19	`return res`