Skip to main content

59. Combinations

mediumAsked at Reddit

Generate all combinations of k numbers from 1 to n. Reddit uses this to test backtracking with start-index — the same enumeration shape they'd use when picking k subreddits for an admin notification A/B test.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common backtracking question.

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 enumeration

Iterate over all 2^n masks; keep those with popcount k.

Time
O(2^n * n)
Space
O(2^n * k)
// Anti-pattern: 2^n masks for combinations is wasteful when k << n.

Tradeoff: TLE for n=20.

2. Backtracking with start-index (optimal)

Recurse with start. At each level pick i from [start, n]; pass i + 1.

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

Tradeoff: The 'i <= n - (k - current.length) + 1' prune avoids descending into branches that can't fill k slots.

Reddit-specific tips

Reddit interviewers grade on the pruning step. Bonus signal: derive the prune bound — at depth d we need k - d more numbers; the largest valid start is n - (k - d) + 1.

Common mistakes

  • Forgetting i + 1 (allows reusing the same number).
  • Not pruning the upper bound — wastes time on impossible branches.
  • Pushing current directly without copy.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Combination Sum (LC 39).
  • Subsets (LC 78) — all combinations of all sizes.
  • Combination Sum III (LC 216) — sum constraint.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why prune the loop's upper bound?

Without pruning, you descend into branches like start=4, k=3, n=5 — can't possibly fill 3 slots.

Iterative version?

Lexicographic next-combination algorithm exists but is harder than backtracking.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →