列舉所有組合（enumerating all combinations）

組合是一種「順序無關、大小固定」的選擇：從 n 件物品中恰好挑 k 件，而 {蘋果, 梨} 與 {梨, 蘋果} 是同一個選擇。從 10 人中選 3 人組委員會、從一副牌發 5 張手牌、挑 k 項特徵來測試——這些要的是組合，不是排列。n 件物品大小為 k 的組合數是二項式係數 C(n, k) = n! / (k! (n-k)!)，常讀作「n 取 k」。

要把它們列舉到不漏不重，標準訣竅是堅持「被選元素以遞增的索引順序出現」。如此一來每個組合都恰有一個正規表示法，自動消除重複。一個乾淨的遞迴逐元素地建組合：嘗試納入仍可用的最小索引，遞迴從更大的索引去填其餘 k-1 格，然後回溯改試下一個索引。因為每個被選序列都遞增，沒有組合會被生成兩次；又因為遞迴走遍所有長度為 k 的合法遞增序列，沒有組合被跳過。對 {1,2,3,4} 取 2，這給出 12、13、14、23、24、34——恰好 C(4,2) = 6 個組合。

組合介於子集合與排列之間：列舉所有子集合就是 k = 0, 1, ..., n 之所有組合的聯集（所以 C(n,k) 的總和 = 2^n）。當問題固定了大小時，組合列舉就是對的工具——恰選 k 台伺服器、抽 k 件樣本、檢驗所有 k 元子集合是否具某性質。成本是 Theta(k * C(n, k))，這仍可能巨大（C(50, 25) 超過 10^14），所以一如往常，它是個基準線，當 k 或 n 變大時就用更聰明的方法取代。