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

You may return the answer in any order.

Examples

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints

  • 1 <= n <= 20
  • 1 <= k <= n

Thinking Process

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

You may return the answer in any order.

  • Build solution incrementally; undo (backtrack) when constraints fail.
  • Prune branches early to avoid exploring invalid partial states.
  • Sort input to skip duplicate combinations efficiently.
Backtracking tree start choose → explore → undo (prune)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Choose / explore / unchoose (this problem) O(2^n) O(n) Subsets, combinations
Constraint pruning Reduced search O(n) Early exit on invalid partial
Sort + skip duplicates O(2^n) O(n) Combination sum II style
Path recording O(n!) worst O(n) Permutations

Solution

Solution: Backtracking with DFS

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        result = []
        path = []
        self.dfs(n, k, path, 1, result)
        return result

    def dfs(self, n: int, k: int, path: list[int], first_num: int, result: list[list[int]]) -> None:
        if len(path) == k:
            result.append(path[:])
            return

        for i in range(first_num, n + 1):
            path.append(i)
            self.dfs(n, k, path, i + 1, result)
            path.pop()

Solution Explanation

Approach: Choose / explore / unchoose (this problem)

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

How the code works:

  • Build solution incrementally; undo (backtrack) when constraints fail.
  • Prune branches early to avoid exploring invalid partial states.
  • Sort input to skip duplicate combinations efficiently.

Walkthrough — input n = 4, k = 2, expected output [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]:

There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Algorithm Explanation:

  1. Initialize: Start with empty path and first_num = 1
  2. Base case: If path.size() == k, we have a valid combination
  3. Recursive case:
    • Try each number from first_num to n
    • Add current number to path
    • Recursively explore with first_num = i + 1 (avoid duplicates)
    • Backtrack by removing the number from path

Example Walkthrough:

For n = 4, k = 2:

dfs(4, 2, [], 1, result)
├── i=1: path=[1]
│   └── dfs(4, 2, [1], 2, result)
│       ├── i=2: path=[1,2] → result=[[1,2]]
│       ├── i=3: path=[1,3] → result=[[1,2],[1,3]]
│       └── i=4: path=[1,4] → result=[[1,2],[1,3],[1,4]]
├── i=2: path=[2]
│   └── dfs(4, 2, [2], 3, result)
│       ├── i=3: path=[2,3] → result=[[1,2],[1,3],[1,4],[2,3]]
│       └── i=4: path=[2,4] → result=[[1,2],[1,3],[1,4],[2,3],[2,4]]
└── i=3: path=[3]
    └── dfs(4, 2, [3], 4, result)
        └── i=4: path=[3,4] → result=[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Time Complexity: O(C(n,k) × k)

  • Number of combinations: C(n,k) = n! / (k! × (n-k)!)
  • Each combination: Takes O(k) time to build
  • Total: O(C(n,k) × k)

Space Complexity: O(k)

  • Recursion depth: O(k) - maximum depth of recursion
  • Path storage: O(k) - stores current combination
  • Result storage: O(C(n,k) × k) - not counted in auxiliary space

    Key Points

  1. Backtracking: Use DFS with backtracking to explore all combinations
  2. Avoid duplicates: Start from first_num and only consider larger numbers
  3. Efficient pruning: Stop when path size equals k
  4. Order preservation: Combinations are generated in lexicographical order

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Backtracking, Recursion, Combinations, DFS, Medium

Key Takeaways

  • Build solution incrementally; undo (backtrack) when constraints fail.
  • Prune branches early to avoid exploring invalid partial states.
  • Sort input to skip duplicate combinations efficiently.

References

Template Reference