Problem Statement
Combinations
You are given two numbers, n and k. Think of a bag of number cards from 1 up to n. You want to find every way to pick exactly k of those cards. The order you pick them in does not matter, so picking card 1 then card 2 counts as the same group as picking card 2 then card 1. For n = 4 and k = 2, one valid group is [1, 2], and you want all such groups. The tool for this is backtracking, which means you try building a group one card at a time, and whenever a path leads nowhere useful you step back and try a different card.
Signals to notice
Brute force first
Not applicable — enumeration IS the task.
The key insight
Backtracking from current index. Choose numbers ≥ last chosen to avoid duplicate combinations. When k numbers chosen, record. O(C(n,k) × k).
Trace it on n=4, k=2
backtrack(1,[]): combo size 0<2; loop i in [1,2,3] (bound n-(k-0)+1=3) i=1 -> combo=[1]; backtrack(2,[1]): size 1<2; loop i in [2,3,4] (bound 4) -> record [1,2],[1,3],[1,4]; pop back to combo=[] i=2 -> combo=[2]; backtrack(3,[2]): loop i in [3,4] -> record [2,3],[2,4]; pop back to combo=[] i=3 -> combo=[3]; backtrack(4,[3]): loop i in [4] -> record [3,4]; pop back to combo=[] i=4 pruned (start 4 > bound 3); top-level loop ends return result = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
What must stay true
Always choosing from [start, n] produces sorted combinations, eliminating permutations of the same set.
Shape of the loop
backtrack(start, combo):
if len(combo) == k: record copy(combo); return
for i from start to n-(k-len(combo))+1: # prune: leave enough room
combo.push(i)
backtrack(i+1, combo) # only larger numbers next
combo.pop() # undo choicePseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Starting from 1 each time — that generates permutations. Use start = last + 1.