enumerating all combinations

A combination is a selection where order does not matter and the size is fixed: pick exactly k of the n items, and {apple, pear} is the same choice as {pear, apple}. Choosing a committee of 3 from 10 people, dealing a 5-card hand from a deck, picking k features to test — these ask for combinations, not permutations. The number of size-k combinations of n items is the binomial coefficient C(n, k) = n! / (k! (n-k)!), often read n choose k.

To enumerate them without missing or repeating any, the standard trick is to insist the chosen elements come in increasing index order. Then each combination has exactly one canonical representation, which kills duplicates automatically. A clean recursion builds combinations element by element: try to include the smallest still-available index, recurse to fill the remaining k-1 slots from larger indices, then backtrack and try the next index instead. Because every chosen sequence is increasing, no combination is generated twice, and because the recursion explores all valid increasing sequences of length k, none is skipped. For 2 of {1,2,3,4} this yields 12, 13, 14, 23, 24, 34 — exactly C(4,2) = 6 combinations.

Combinations sit between subsets and permutations: enumerating all subsets is the union of all combinations over k = 0, 1, ..., n (so sum of C(n,k) = 2^n). Combination enumeration is the right tool when the problem fixes a size — choose exactly k servers, sample k items, test all k-element subsets for a property. The cost is Theta(k * C(n, k)), which can still be enormous (C(50, 25) is over 10^14), so as always it is a baseline you replace with a smarter method when k or n grows.