NeetCode #491LC-77MediumBacktrackingNC 250
← Back to All Problems#491 · #77 · Combinations(组合)
📌 Problem Statement & Constraints
Given two integers
n and k, return all possible combinations of k numbers chosen from the range 1..n. Constraints: 1 <= n <= 20, 1 <= k <= n.💡 Core Algorithmic Approaches
- Backtrack over the starting value, appending values in increasing order.
- Because the loop only moves forward, each combination is generated exactly once (no deduplication needed).
- A useful pruning: if the remaining values cannot fill the combination, stop the loop early.
- The answer is recorded when the path length reaches
k.
💻 Benchmark Python3 Implementation
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def dfs(start: int, path: List[int]) -> None:
if len(path) == k:
res.append(path[:])
return
# need (k - len(path)) more values from [start, n]
for v in range(start, n + 1):
if n - v + 1 < k - len(path):
break # not enough values left
path.append(v)
dfs(v + 1, path) # increasing order -> no duplicates
path.pop()
dfs(1, [])
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(C(n, k) * k): the number of combinations times the copy cost.
💾 Space Complexity
O(k) for the recursion path.
⚠️ Interview Pitfalls & Follow-ups
- Recursing with
vinstead ofv + 1: values could repeat, producing invalid combinations. - Omitting the early break: correct but explores useless branches.
- Generating permutations and deduplicating: wasteful, since order does not matter here.
- Starting the range at 0: the values are
1..n.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.