Skip to main content

61. Combinations

mediumAsked at Ola

Return all combinations of k numbers chosen from 1..n.

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]]

Approaches

1. Bitmask enumerate

Enumerate every n-bit mask and keep masks with k bits set.

Time
O(2^n * n)
Space
O(C(n,k))
// for mask in 0..(1<<n): if popcount(mask)==k, decode the set

Tradeoff:

2. Backtracking with start index

Recurse selecting numbers >= start until path has k elements.

Time
O(C(n,k) * k)
Space
O(k)
function combine(n, k) {
  const out = [];
  const dfs = (start, path) => {
    if (path.length === k) { out.push([...path]); return; }
    for (let i = start; i <= n; i++) {
      path.push(i);
      dfs(i+1, path);
      path.pop();
    }
  };
  dfs(1, []);
  return out;
}

Tradeoff:

Ola-specific tips

Ola checks that you keep start-index discipline to avoid duplicates; tie it to selecting subsets of drivers from a vehicle pool for a feature rollout.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Combinations and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →