Skip to main content

77. Combinations

medium

Return every possible combination of k numbers chosen from the range [1, n]. Cleanest demonstration of the 'pick i from [start, n]' recursion pattern that powers Combination Sum, Subsets, and friends.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

Input
n = 4, k = 2
Output
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse with a start index and a current path. Snapshot the path when its length is k.

Hint 2

At each call, loop i from start to n: append i, recurse with start = i + 1, pop.

Hint 3

Pruning: there's no point starting at i if you can't reach k items. Stop the loop when i > n - (k - path.length) + 1.

Hint 4

That prune turns a slow brute force into a tight optimal traversal.

Solution approach

Reveal approach

Standard combination backtracking: recurse with (start, path). Base case: path.length == k -> push a copy to result, return. Recursive case: for i from start to n inclusive, append i, recurse(i + 1, path), pop. The 'i + 1' is what enforces strictly increasing order and prevents duplicate combinations. Critical prune: replace 'i <= n' with 'i <= n - (k - path.length) + 1' — if there aren't enough remaining numbers to fill the path to length k, stop iterating. Without the prune you generate a lot of dead branches; with it you only visit nodes that can lead to a complete combination. Time is O(k * C(n,k)); space O(k) recursion.

Complexity

Time
O(k * C(n,k))
Space
O(k)

Related patterns

  • backtracking
  • recursion
  • combinatorics

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Combinations and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →