Order does not matter
A combination picks k elements from n where order is irrelevant, so the pair one then two is the same as two then one. The count is n choose k. Combinations sit between subsets, which fix no size, and permutations, which care about order.
Start index drives it
The trick that keeps each combination unique is a start index. At each level you only consider elements from the current index onward, never looking back. This enforces an increasing order on the chosen indices and rules out reordered duplicates.
- If the path already holds k elements, record it and return.
- Otherwise loop from the start index to the end, append each element, recurse with the next index, then pop.
Pruning short tails
A powerful optimization stops exploring branches that cannot reach k elements. If the elements remaining from the current index are fewer than the slots still needed, abandon the branch immediately. This trims a large share of dead recursion near the end of the loop.
Key idea
A monotonically increasing start index makes every combination appear exactly once, and pruning branches that lack enough remaining elements cuts the wasted work sharply.