Free Backtracking lessonsBacktracking · Stage 1 · Combinations · Step 1

Combinations of size k

Pick numbers moving forward only, so every combination shows up exactly once. About 8 minutes.

Pick forward, never back

Subsets asked "in or out" for every item. Combinations ask something subtler: which k numbers do you pick out of n? If you could add any number at any moment, then 1 and 3 would be counted as a different answer from 3 and 1, even though it is the same pair.

The fix is a starting point. Once you have looked at a number, you may only add numbers after it, like choosing seats in a row from left to right.

Loop, don't branch: try each number from the starting point onwards.

Move forward only: the next call starts just past the number you picked.

n = 4, k = 2 · after picking a number, only later numbers are allowed

curr: [1]

Pick 1. The next pick starts from 2.

Move 1 of 5

Stop at size k, not at the end of the range

There is no "reached the last number" base case here. You are not deciding in or out for every number; you are building a list until it holds exactly k of them.

As soon as the list has k entries, save a copy and return. The loop one level up carries on trying later numbers by itself.

Base case: the list has k entries, so save a copy and return.

Copy, don't share: the working list keeps changing, so save a copy of it.

In code

res = []
def backtrack(start, curr):
    if len(curr) == k:
        res.append(list(curr))
        return
    for num in range(start, n + 1):
        curr.append(num)
        backtrack(num + 1, curr)
        curr.pop()
backtrack(1, [])
return res

Quick check

Why does the recursive call use backtrack(num + 1, curr) instead of backtrack(num, curr) or backtrack(0, curr)?

ASo a number already tried is never tried again in this branch, and combinations can't be reordered into duplicates
BIt's purely a speed optimization — starting from 0 would still give correct, just slower, results
CIt marks the base case, the same way idx == n does for subsets

Show the answer

So a number already tried is never tried again in this branch, and combinations can't be reordered into duplicates. Moving start forward guarantees every combination is built with strictly increasing numbers, so each one is produced exactly once.

Your problem

Combinations of size k

Given two integers n and k, return every combination of k numbers chosen from 1 to n, with no number repeated within a combination. List the numbers within each combination in increasing order, and list the combinations themselves in lexicographic order.

Example

n = 4, k = 2 → [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

0 ≤ k ≤ n ≤ 10

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.