POJ 2245 Lotto：標準 DFS 組合生成（字典序輸出）

題目大意

給定 k（6 < k < 13）個已排序數字，輸出所有 6 元組合，每行一組，組內遞增，組間按字典序。多測資，k=0 結束，測資間空一行。

DFS 組合生成模板

標準「選 / 不選」遞迴，參數 (pos, cnt)：

void dfs(int pos, int cnt) {
    if (k - pos + 1 < 6 - cnt) return; // 剪枝：剩餘數不足
    if (cnt == 6) { output current comb; return; }
    comb[cnt] = a[pos];
    dfs(pos + 1, cnt + 1); // 選
    dfs(pos + 1, cnt);     // 不選
}

• 輸入數組 a[1..k] 已遞增，DFS 先「選」後「不選」天然產生字典序。
• 剪枝條件 k - pos + 1 < 6 - cnt 大幅減少遞迴節點。

輸出格式細節

• 組內數字間單空格，行末無多餘空格：printf("%d", comb[0]); for(i=1..5) printf(" %d", comb[i]); puts("");
• 測資間空一行：用 firstCase 標記，非首測資前印 puts("")。

複雜度

C(k, 6) ≤ C(12, 6) = 924，DFS 瞬間完成。

總結

本題是「組合生成 + 字典序輸出」的入門模板。核心在於：輸入已排序 + DFS 先選後不選 = 自動字典序，並善用「剩餘數不足」剪枝。代碼極短，適合作為 DFS 組合生成的標準參考實現。