How do you solve Combinations?

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.

Combinations

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.

Q: 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.

Medium Backtracking

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

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(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.

Pattern Spotlight

Backtracking (State Restoration)

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.

Solution

Python

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

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.

Recursively Build Combinations with Choose-Explore-Unchoose Pattern

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

Return the Complete List of Combinations

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

2 more steps with full analysis available on Pro.

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.

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

Test Your Understanding

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

See the answer with Pro.

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`