⚡Flashcard Drill➔
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

  1. Backtrack over the starting value, appending values in increasing order.
  2. Because the loop only moves forward, each combination is generated exactly once (no deduplication needed).
  3. A useful pruning: if the remaining values cannot fill the combination, stop the loop early.
  4. 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 v instead of v + 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems