Skip to main content

61. Combinations

mediumAsked at Snowflake

Generate all combinations of k numbers from 1..n. Snowflake asks this as a backtracking template — the same enumeration shape as choosing k tables to join (Selinger-style join-order enumeration).

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to lead into join-order subset enumeration.
  • LeetCode Discuss (2025-08)— Reported at Snowflake new-grad screens.

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. Backtracking without pruning

Backtrack picking next numbers; emit when path is k long.

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

Tradeoff: Correct but explores some hopeless branches (where remaining numbers can't fill k).

2. Backtracking with prune (optimal)

Cap the loop upper bound at n - (k - path.length) + 1 — prevents exploration when there aren't enough remaining numbers.

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

Tradeoff: Same asymptotic but with much tighter constants. Standard backtracking-with-pruning template.

Snowflake-specific tips

Snowflake interviewers want the prune condition stated explicitly. Bonus signal: connect to join-order optimization — Selinger DP enumerates subsets of tables, computing min-cost plan per subset. The combinations enumeration is the same shape (subsets of size k from n tables).

Common mistakes

  • Forgetting start index — emits permutations, not combinations.
  • Not pruning the loop bound — accepts but slower.
  • Pushing path directly instead of [...path] — all results share the same array.

Follow-up questions

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

  • Subsets (LC 78).
  • Combination Sum (LC 39).
  • Selinger join-order optimization.

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 upper bound?

If we need 'need' more numbers, the smallest valid start is n - need + 1. Numbers beyond that can't fill the rest. Pruning skips hopeless branches without the recursion needing to fail.

How does this connect to join orders?

Selinger DP iterates subset sizes 1..n. For each size k, it enumerates C(n, k) subsets — exactly this problem's enumeration. For each subset, it computes the best plan to join those tables.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →