77. Combinations
Model: qwen3.5:9b
Topics: Backtracking
FAANG asked: 1
Acceptance rate: 57.9%
Problem Breakdown
We need to generate all unique subsets of size k from a set containing integers [1, n].
- Inputs: Two positive integers
nandk, where . - Outputs: A list of lists. Each inner list represents one valid combination sorted in ascending order (e.g.,
[2, 4]). The outer list can be returned in any order. - Implicit Constraints: Since we are dealing with combinations (order within the subset doesn’t matter),
[1, 3]is identical to[3, 1]. We must ensure each unique set appears exactly once. Given , standard integer types won’t overflow during counting logic, but memory usage depends on output size ().
Intuition
A brute-force approach might be generating all subsets of the range [1, n] and filtering those with length k. However, that generates candidates. Since we only want combinations (not permutations), order matters for generation but not for validity.
The key insight is to build valid sequences incrementally using Backtracking. At each step of the recursion, we decide whether to include a number or skip it. To avoid duplicates and ensure sorted output naturally:
- We iterate through numbers from
startup ton. - Once we pick a number for our current combination slot, all subsequent picks must be strictly greater than that number (to maintain ascending order). This prevents generating
[3, 1]after picking3, because the next loop index will start at4.
Approach
We use Depth-First Search (DFS) via recursion.
- Define a helper function
backtrack(start_index)which takes the current starting number to consider for inclusion. - Base Case: If the length of our current path equals
k, we have found a valid combination; append it to results and return. - Recursive Step: Iterate through numbers from
start_indexup to where enough elements remain to complete the combination:- Add the current number
ito the path. - Recurse with
backtrack(i + 1). The next pick must be greater thani, so we passi + 1as the new start index. - Backtracking: Remove the last element from the path before returning (undoing the choice).
- Add the current number
This ensures every valid combination is visited exactly once in lexicographical order without generating permutations or duplicates.
Complexity Analysis
- Time Complexity: , where is “n choose k”. We visit each node in the recursion tree that corresponds to a partial valid combination and perform work proportional to
k(copying/adding elements). Since we must output every element of every combination, this is optimal. - Space Complexity: . This accounts for the recursion stack depth and the temporary path list used during traversal. We do not count the space required for the result array in standard complexity analysis unless specified otherwise (though technically it’s part of total memory usage).
Solution
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
# Helper function for backtracking
# path stores the current combination being built
# start_idx ensures we only pick numbers greater than or equal to previous picks
def backtrack(start_idx):
if len(path) == k:
res.append(list(path)) # Append a copy of the valid combination
return
# Optimization: Prune search space.
# We need (k - len(path)) more numbers, so we only iterate up to n - remaining_needed + 1
for i in range(start_idx, n - k + len(path) + 2):
path.append(i) # Choose number 'i'
backtrack(i + 1) # Explore next level with start index > current
path.pop() # Backtrack: remove last element to try other numbers
path = []
backtrack(1)
return res
Edge Cases Handled
- k == n: The loop range and recursion depth naturally result in a single combination
[1, 2, ..., n]. No extra checks needed. - k == 1: The base case triggers immediately after picking each number from
1ton, resulting in individual lists like[1], [2], .... - Pruning Logic: Although not strictly required for , the loop range calculation (
range(start_idx, n - k + len(path) + 2)ensures we don’t iterate past numbers that can possibly complete a combination of sizek, preventing unnecessary recursive calls.