Faangprep Logo
Log inStart free
Browse curriculum

Combinations

Generate every way to choose k numbers from 1 to n with backtracking that only moves forward, so each set is built exactly once.

MediumSolve on LeetCode

Problem Understanding

Combinations: given integers n and k, return every combination of k numbers chosen from 1 to n, in any order.

Example: n = 4, k = 2 returns [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]], which is C(4, 2) = 6 combinations.

The Intuition: Only Move Forward

A combination is a set, so [1, 2] and [2, 1] are the same answer. The trick is to build every set in increasing order, so each one has exactly one way to be built. That is a backtracking search with a start index:

  1. Try every number from start to n.
  2. Append it and recurse with start = i + 1, so later picks are always larger.
  3. Pop it and try the next number.
  4. When the path has k numbers, record it.

Compare Permutations, where order matters and a used array replaces the start index, and Subsets, which records a path of every length.

Interactive Walkthrough

The numbers 1 to n are on top. Numbers in the path are tinted, and numbers below the current start are greyed out: this branch can never pick them again. Combinations collect beside the figure. Try Choose 3 of 5 to see all 10.

Dry Run Table

Input: n = 4, k = 2

First pick Second pick from Recorded
1 2, 3, 4 [1,2], [1,3], [1,4]
2 3, 4 [2,3], [2,4]
3 4 [3,4]
4 (none) —

Answer: 6 combinations.

The Solution Template

Backtracking with a start index. C sizes the result as C(n, k) up front, computed exactly with a running product.

Combinations Code
1var combine = function(n, k) {
2    const res = [], path = [];
3    const backtrack = (start) => {
4        if (path.length === k) {
5            res.push([...path]);
6            return;
7        }
8        for (let i = start; i <= n; i++) {
9            path.push(i);
10            backtrack(i + 1);
11            path.pop();
12        }
13    };
14    backtrack(1);
15    return res;
16};

Edge Cases & Common Mistakes

  • k = n: exactly one combination, all the numbers.
  • k = 1: n single-number combinations.
  • Recursing with start instead of i + 1: reuses numbers and produces duplicates like [1, 1].
  • Appending the path itself: later pops empty it; append a copy.
  • No pruning: branches that cannot reach k numbers still run; loop only to n − (k − len(path)) + 1 to skip them.

Summary

Backtrack with a start index: for each i from start to n, append it, recurse with start = i + 1, and pop it. Record the path whenever it holds k numbers. Building each set in increasing order makes every combination appear once. O(k · C(n, k)) time.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Permutations II

Next

Letter Case Permutation

The approach, step by step

  1. Start at 1

    Call backtrack(start = 1) with an empty path.

  2. Choose forward

    For each i from start to n: append i, recurse with start = i + 1, then pop i.

  3. Record full paths

    When the path holds k numbers, copy it into the result and return.

Frequently asked questions

How does backtracking avoid duplicate combinations?

Each call only tries numbers from start to n, and the recursive call uses start = i + 1. Every combination is therefore built in increasing order, so {1, 2} is produced but {2, 1} never is. Each set appears exactly once.

How is Combinations different from Permutations?

Permutations care about order, so every unused number is tried at every level with a used array. Combinations do not, so each level only looks forward from a start index, and no used array is needed.

Can the search be pruned?

Yes. If fewer numbers remain than slots left to fill, the branch cannot finish. Loop i only up to n − (k − len(path)) + 1 to skip those branches; the output is the same, with fewer dead calls.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description