Combinations
Combinations is LeetCode 77 (Medium). You are given two integers n and k, and must return every way to choose k distinct numbers from the range 1 to n.
- Each number can appear at most once in a combination.
- Order inside a combination does not matter, so the same set must not be returned twice in two different orders.
- The combinations themselves can be returned in any order.
n is at most 20 and k at most n, so the output alone can run to six figures of lists. The work is dominated by producing them, which makes a search that never wastes a branch the goal.
- 1 <= n <= 20
- 1 <= k <= n
Intuition
A combination is a set, so order does not matter. The simplest way to never produce the same set twice is to build every combination in increasing order: then each set has exactly one spelling, and its shuffled versions can never be built.
That turns the problem into a search tree with one number per level, where each level only picks numbers larger than the last. When the path is full it is a combination; the search then backtracks, removing the last number to try the next one. Pruning keeps it fast: a branch that cannot possibly collect k numbers before running out is never started.
"Return all" subsets, orderings or selections is backtracking, and the combinations LeetCode problem is the plainest version: choose k of n, no reuse, order not mattering, so a start index only moves forward. Combination Sum (39) keeps start on the same number to allow reuse; Permutations (46) drops start and uses a used array instead.
Approach
Before reading on, list all combinations for n = 4, k = 2 by hand, in order. Notice which first numbers you never needed to try, and why.
Two ways to solve it
At each level, loop the next number from start up to n - need + 1, so every branch can still reach k numbers.
- Pruning: branches that run out of numbers are never opened.
- Depth: at most
kframes, one per chosen number. - Work: close to the cost of copying the output.
This is the version interviewers expect.
Walk the numbers 1 to n and, for each one, branch twice: include it in the path or leave it out.
- Dead branches: many skip paths end with too few numbers.
- Depth: up to
nframes, one per number decided. - Readability: the same include/exclude shape as subsets.
Easy to derive, but it wastes work.
Both copy the same C(n, k) lists, but the loop never starts a branch that cannot finish, while pick / skip explores up to 2ⁿ paths. The steps, code and live demo below follow the loop, and the pick / skip code is further down.
Keep one path and a start index
Keep path, the numbers chosen so far in increasing order, and start, the smallest number the next pick may use. Passing start down instead of always looping from 1 is what enforces increasing order, so no set is ever built twice.
Record when the path is full
If len(path) == k, append a copy of path to the result and return. In the combinations Python code that copy is path[:]; appending path itself stores a reference to the list that backtracking keeps emptying, so every saved answer ends up blank.
Otherwise try each allowed next number
need = k − len(path)numbers are still missing.- Loop
numfromstartton − need + 1. - Append
num, recurse withstart = num + 1, then popnum(backtrack).
Why the pruning bound is right
After picking num, the remaining need − 1 numbers must come from num + 1 … n, which has n − num numbers. That requires n − num ≥ need − 1, so num ≤ n − need + 1. Any larger pick starts a branch that can never finish.
Combinations solution in Python | C++ | Java
n − need + 1 meant no branch was ever started that could not reach 2 numbers, so every leaf of the search is an answer.n − need + 1 meant no branch was ever started that could not reach 3 numbers, so every leaf of the search is an answer.n − need + 1 meant no branch was ever started that could not reach 3 numbers, so every leaf of the search is an answer.Pick / skip recursion
pick(i) decides number i: first it adds i and recurses on i + 1, then it removes i and recurses on i + 1 without it. A path is recorded as soon as it holds k numbers.
Common pitfalls
Appending the path itself instead of a copy
result.append(path)
result.append(path[:])
Every entry would be the same list object. After the search it has been popped back to empty, so the result is a list of empty lists: [[], [], …].
Restarting the loop from 1
for num in range(1, n + 1):
if num in path:
continuefor num in range(start, n - need + 2):
That builds permutations, not combinations: [1, 2] and [2, 1] both appear. Moving start forward keeps every path increasing, so each set is built once.
Recursing with start instead of num + 1
backtrack(start + 1)
backtrack(num + 1)
The next pick must be larger than the number just chosen, not larger than where this level began. With start + 1, choosing 3 then allows 2 next, producing [3, 2] and duplicates.
Complexity
Combinations FAQ
How do you get combinations in Python without writing the search?
Use itertools.combinations: list(combinations(range(1, n + 1), k)) from itertools returns tuples in lexicographic order. On LeetCode 77 convert each tuple with list(). Interviews usually still ask for the backtracking version, since itertools combinations hides the algorithm.
How many combinations are there?
C(n, k) = n! / (k! (n − k)!). For n = 4, k = 2 that is 6; for n = 5, k = 3 it is 10.
What is the difference between combinations and permutations?
Combinations ignore order: {1, 2} and {2, 1} are one combination. Permutations count each ordering separately, so there are k! times as many. In code, combinations move a start index forward; permutations try every unused number at every level.