59. Combinations

Q: Why does the pruning work?

If we need `needed` more numbers and only `n - i + 1` remain, we must stop iterating once i > n - needed + 1 (because all remaining picks must come from [i, n], and we need at least `needed` of them).

mediumAsked at Salesforce

Return all possible combinations of k numbers chosen from 1..n. Salesforce uses this as a backtracking template — relevant to their permission-set selection logic.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

Glassdoor (2026-Q1)— Salesforce uses combinatorial enumeration for permission-set role analysis.
LeetCode Discuss (2025)— Common pairing with Permutations.

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

Try every subset; keep those of size k.

Time: O(2^n * k)
Space: O(k)

function combine(n, k) {
  const result = [];
  function dfs(i, path) {
    if (path.length === k) { result.push([...path]); return; }
    if (i > n) return;
    dfs(i + 1, path);
    path.push(i); dfs(i + 1, path); path.pop();
  }
  dfs(1, []);
  return result;
}

Tradeoff: Works but enumerates exponentially many subsets. Wasted work.

2. Backtracking with pruning

Start with i = 1. At each level pick j in [i, n]; recurse with j+1. Prune when remaining slots > 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 needed = k - path.length;
    for (let i = start; i <= n - needed + 1; i++) {
      path.push(i);
      dfs(i + 1, path);
      path.pop();
    }
  }
  dfs(1, []);
  return result;
}

Tradeoff: The pruning `i <= n - needed + 1` skips branches that can't complete. Critical optimization.

Salesforce-specific tips

Salesforce uses this pattern for permission-set audit (which combinations of permissions can a role have?). They grade on whether you spot the pruning condition that keeps the search tight. Bonus signal: discuss that the pruning saves significant work when k is close to n.

Common mistakes

Forgetting to slice path when pushing — same reference appears in all results.
Using start = i (not i+1) — generates duplicates with reuse.
Skipping the pruning — still works but wastes time exploring impossible branches.

Follow-up questions

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

Permutations (LC 46) — order matters.
Subsets (LC 78) — all sizes.
Combination Sum (LC 39).

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 does the pruning work?

If we need `needed` more numbers and only `n - i + 1` remain, we must stop iterating once i > n - needed + 1 (because all remaining picks must come from [i, n], and we need at least `needed` of them).

Why dfs(i+1, ...) and not dfs(i, ...)?

Because each number can only be picked once. i+1 advances the candidate pool past the just-picked number.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →