What pattern does Combinations use?

The Pattern: Backtracking (State Restoration) The Heuristic: For combination generation problems, use a recursive 'choose, explore, un-choose' pattern that incrementally builds partial solutions and restores state after exploring each branch to efficiently enumerate all valid combinations without duplicates.

Combinations - LeetCode Solution & Explanation

Q: What is the time complexity of Combinations?

O(C(n, k) * k). The algorithm generates all combinations of size k from n elements, which is C(n, k). Each combination requires O(k) time to copy into the result list.

Problem

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

1 ≤ n ≤ 20
1 ≤ k ≤ n

Example

Input: n = 4, k = 2

Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

The brute-force approach would generate all subsets of [1,2,3,4] and filter those of size 2, which is inefficient. Instead, the backtracking algorithm incrementally builds combinations by exploring each candidate number starting from the current index, adding it to the current combination, recursing to build further, and then removing it to explore alternative paths. This systematic exploration prunes unnecessary branches and ensures all unique combinations are generated without duplicates.

Approach

Straightforward Solution

A naive approach would generate all subsets of [1..n] and then filter those with size k, resulting in O(2^n) time complexity, which is inefficient for larger n.

Core Observation

The problem requires enumerating all k-sized subsets from a set of n elements, which naturally forms a combinatorial search space with overlapping subproblems and branching decisions.

Path to Optimal

Recognizing the problem as a combinatorial enumeration task, backtracking is the natural fit. The key insight is to build combinations incrementally, choosing each number starting from the current index to avoid duplicates and ensure ascending order. By pruning branches once the combination reaches size k, the algorithm avoids exploring unnecessary paths, reducing the search space significantly.

Optimal Approach

Use a recursive backtracking function that maintains the current combination and the next candidate number to consider. At each step, if the combination size equals k, add a copy to the results. Otherwise, iterate from the current candidate to n, append the number, recurse with the next candidate, and then remove the number to backtrack. This approach systematically explores all valid combinations with pruning and ordering guarantees.

Time

O(C(n, k) * k)

The algorithm generates all combinations of size k from n elements, which is C(n, k). Each combination requires O(k) time to copy into the result list.

Space

O(k)

The recursion stack and current combination list use O(k) space, which is the maximum depth and size of the partial solution during backtracking. The output space is not counted here.

Solution

1class Solution:
  def combine(self, n: int, k: int) -> List[List[int]]:
      def backtrack(curr, i):
          if len(curr) == k:
              ans.append(curr[:])
              return
          
          for num in range(i, n + 1):
              curr.append(num)
              backtrack(curr, num + 1)
              curr.pop()
      
      ans = []
      backtrack([], 1)
      return ans

Step-by-Step Solution

1

Initialize Result List and Start Backtracking from 1

13ans = []
14backtrack([], 1)

Objective

To prepare the container for storing all valid combinations and initiate the recursive exploration from the first candidate number.

Key Insight

Starting the backtracking with an empty current combination and the first candidate number 1 sets the stage for systematic exploration. The result list collects all valid combinations found during recursion. This initialization is essential to separate the recursive logic from the storage of final answers.

Interview Quick-Check

Core Logic

The result list stores all valid combinations found by the recursive backtracking process.

State & Boundaries

Starting the recursion at 1 ensures all numbers from 1 to n are considered in ascending order.

2

Recursively Build Combinations with Choose-Explore-Unchoose Pattern

3def backtrack(curr, i):
  if len(curr) == k:
      ans.append(curr[:])
      return
  for num in range(i, n + 1):
      curr.append(num)
      backtrack(curr, num + 1)
      curr.pop()

Objective

To explore all possible combinations by incrementally adding numbers, recursing, and then removing them to backtrack.

Key Insight

The backtracking function embodies the 'choose, explore, un-choose' pattern: it chooses a number by appending it to the current combination, explores further combinations recursively starting from the next number, and then un-chooses by popping the last number to restore state. This pattern ensures exhaustive and non-redundant exploration of all valid combinations. The base case triggers when the current combination reaches size k, at which point a copy is added to the results.

Interview Quick-Check

Core Logic

The recursive function explores all combinations by iterating from the current candidate to n, choosing each number, recursing, and then backtracking.

State & Boundaries

The base case is when the current combination size equals k, signaling a complete valid combination.

Common Pitfalls & Bugs

Failing to pop the last number after recursion leads to incorrect combinations due to shared mutable state.

Complexity

Pruning the recursion when the combination size reaches k avoids unnecessary exploration, improving efficiency.

3

Return the Complete List of Combinations

15	`return ans`

Objective

To output the final list containing all k-sized combinations generated by backtracking.

Key Insight

After the recursive exploration completes, the result list contains all valid combinations. Returning this list provides the solution to the problem as required.

Interview Quick-Check

Core Logic

Returning the result list after backtracking completes delivers all valid combinations.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 11 Critical

curr.pop()

Remove the last candidate number to backtrack and restore state.

This state restoration is the single most critical line in backtracking; it ensures that after exploring one branch, the algorithm can correctly explore others without carrying over changes, enabling exhaustive and correct enumeration.

Line 4 Critical

if len(curr) == k:

Check if the current combination has reached the target size k.

This base case terminates recursion when a valid combination is formed, ensuring only combinations of size k are added to the results.

Line 5 Critical

ans.append(curr[:])

Add a copy of the current combination to the results list.

Copying the current combination is essential because the list is mutable and will be modified during backtracking; storing a snapshot preserves the valid solution.

Line 8 Core

for num in range(i, n + 1):

Iterate over candidate numbers from the current index to n.

Iterating from the current index ensures combinations are generated in ascending order without duplicates, maintaining correctness and efficiency.

Line 10 Core

backtrack(curr, num + 1)

Recursively explore further combinations starting from the next candidate.

Recursion advances the search by considering subsequent numbers, building on the current partial combination.

Line 6 Core

return

Return immediately after adding a valid combination.

This prevents further exploration once a complete combination is found, pruning the recursion tree and improving efficiency.

Line 9 Core

curr.append(num)

Add the current candidate number to the combination.

Choosing a candidate extends the current partial solution, enabling exploration of deeper combinations.

Line 3 Standard

def backtrack(curr, i):

Define the recursive backtracking function with current combination and start index.

Encapsulating the recursive logic in a helper function allows clean management of the current state and candidate exploration, enabling systematic traversal of the search space.

Line 14 Standard

backtrack([], 1)

Start the backtracking process with an empty combination and starting index 1.

Initiating recursion from 1 ensures all numbers in [1, n] are considered in ascending order, enabling systematic exploration.

Line 13 Standard

ans = []

Initialize the list to store all valid combinations.

This list accumulates all solutions found during recursion, serving as the output container.

Line 15 Standard

return ans

Return the list of all generated combinations.

Returning the accumulated results completes the function, providing the final answer to the caller.

Test Your Understanding

Why does the backtracking function iterate from the current index i to n instead of always starting from 1?

Iterating from the current index i ensures combinations are built in ascending order without duplicates, preventing repeated permutations of the same combination.

Don't just read it. Drill it.

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

Unlock the Combinations drill

or drill a free problem

1	`class Solution:`
2	`def combine(self, n: int, k: int) -> List[List[int]]:`
3	`def backtrack(curr, i):`
4	`if len(curr) == k:`
5	`ans.append(curr[:])`
6	`return`
7
8	`for num in range(i, n + 1):`
9	`curr.append(num)`
10	`backtrack(curr, num + 1)`
11	`curr.pop()`
12
13	`ans = []`
14	`backtrack([], 1)`
15	`return ans`

3	`def backtrack(curr, i):`
4	`if len(curr) == k:`
5	`ans.append(curr[:])`
6	`return`
8	`for num in range(i, n + 1):`
9	`curr.append(num)`
10	`backtrack(curr, num + 1)`
11	`curr.pop()`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Result List and Start Backtracking from 1

Recursively Build Combinations with Choose-Explore-Unchoose Pattern

Return the Complete List of Combinations

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.