Algorithm

Combinations

Backtracking Pattern

Combinations

Given two integers n and k, return every possible combination of k distinct numbers drawn from the range 1 to n inclusive.

A combination is a set, so order carries no meaning: [1,2] and [2,1] are the same combination and exactly one of them must appear in the output. Each number may be used at most once within a combination.

The combinations themselves may be returned in any order. The output contains C(n, k) entries.

CONSTRAINTS
  • 1 <= n <= 20
  • 1 <= k <= n
  • Numbers are drawn from the range [1, n], never 0
  • Each number may appear at most once in a given combination
  • Output size is C(n, k), which peaks near k = n/2
EXAMPLE 1
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Six combinations, matching C(4,2) = 6. Every entry is listed in increasing order, and no pair appears twice — [3,1] is absent because it describes the same set as [1,3].
EXAMPLE 2
Input: n = 4, k = 4
Output: [[1,2,3,4]]
When k equals n there is exactly one way to choose: take everything. The recursion has no real decisions to make, since skipping any number would leave too few remaining.
EXAMPLE 3
Input: n = 1, k = 1
Output: [[1]]
One number, choose one. The smallest possible input, and a useful check that the base case fires correctly rather than returning an empty list.
EXAMPLE 4
Input: n = 5, k = 1
Output: [[1],[2],[3],[4],[5]]
Choosing a single number gives one combination per candidate. Notice each is a one-element list rather than a bare number — the output shape stays consistent regardless of k.
Does [1,2] count as different from [2,1]?
No, they are the same combination and only one may appear. That is the entire difference between this problem and Permutations, and it is what makes the increasing-order trick both possible and necessary.
Can a number be used more than once within one combination?
No — the k numbers are distinct. Reuse is permitted in Combination Sum, and the code difference between the two is a single character, so it is worth being clear about which you are solving.
Do the numbers range from 0 to n-1 or 1 to n?
From 1 to n. The loop bound is therefore n+1 in a language with exclusive ranges, and an off-by-one here silently drops every combination containing n.
How large can the output be?
C(20,10) is 184,756, so the output is large but manageable. Since the answer itself is that size, no approach can be faster than producing it — the goal is to avoid generating anything that is not in the answer.

Pick k numbers from 1..n. Order doesn't matter, so [1,2] and [2,1] are the same set — each must appear once. The trick: only ever pick numbers bigger than the last one you took. Then every set comes out in increasing order and can be built exactly one way, so duplicates are impossible.

The backtracking template

Every problem in this section is the same loop — three beats: choose, explore, un-choose.

python
def backtrack(state):
    if done(state):
        save(state)              # record the finished answer
        return
    for choice in choices(state):    # what can I pick right now?
        if not ok(choice):
            continue                 # prune: skip bad picks early
        apply(choice)                # CHOOSE
        backtrack(next_state)        # EXPLORE
        undo(choice)                 # UN-CHOOSE: put it back

Only four slots change between problems: done, choices, ok (pruning), and how you finish (save every answer, or return True at the first one). Fill those and the problem is solved.

What changes here
- A choice = pick a number num from start..n.
- Choices = numbers greater than the last pick (recurse with num + 1).
- Done = path has k numbers → save it.
- Prune = optional: stop once too few numbers remain to reach length k.
python
def combine(n, k):
    res, path = [], []

    def backtrack(start):
        if len(path) == k:
            res.append(list(path))
            return
        for num in range(start, n + 1):
            path.append(num)          # CHOOSE
            backtrack(num + 1)        # EXPLORE: only bigger numbers
            path.pop()                # UN-CHOOSE

    backtrack(1)
    return res

The one line that matters is backtrack(num + 1): passing num + 1 keeps paths increasing, so no duplicates. Pass num instead and you get Combination Sum; pass start + 1 and you get bugs.

Trace n=4, k=2: from 1 → [1,2],[1,3],[1,4]; from 2 → [2,3],[2,4]; from 3 → [3,4]. Six sets, none repeated — because [2,1] simply can't be built.

Interactive Strategy Visualization

Combinations (N=4, K=2)

Collected: 0 / 6
1
2
3
4
Current Combination
[ ]
Starting search for size 2 combinations from [1, 2, 3, 4].
MINDSET

To avoid duplicates, we only pick numbers strictly larger than our previous pick. This creates a natural ordering and shrinks the search space.

PERFORMANCE

The total number of calls is reduced compared to permutations. We only explore nCk paths where N is the pool size and K is the subset size.

O(N × 2ⁿ) Filter The Power Set
→
O(K × C(n,k)) Start-Index Backtracking
→
O(K × C(n,k)) With Insufficient-Remainder Pruning