441 Lotto

題目連結

題目敘述

在德國樂透中，你必須從集合 {1,2,...,49} 中選出 6 個數字
雖然這樣做並不會增加中獎的機率，但一種常見的策略是選擇一個包含 k 個數字的子集合 S（k > 6）
然後只從 S 中選擇數字來進行多次投注

例如，對於 k = 8 和 S = {1, 2, 3, 5, 8, 13, 21, 34}
共有 28 種可能的投注組合：

[1,2,3,5,8,13]
[1,2,3,5,8,21]
[1,2,3,5,8,34]
[1,2,3,5,13,21]
...
[3,5,8,13,21,34]

你的任務是撰寫一個程式，讀入數字 k 和集合 S
然後列印出所有只從 S 中選擇數字的可能投注組合

輸入說明

輸入檔將包含一個或多個測試案例。

每個測試案例由一行多個以空格分隔的整數組成
該行的第一個整數是數字 k（6 < k < 13）
接下來的 k 個整數指定了集合 S，這些數字按升序排列

當 k 的值為零（0）時，表示輸入結束。

輸出說明

對於每個測試案例，列印出所有可能的投注組合，每個組合佔一行。

每個投注組合中的數字必須按升序排列，並且彼此之間以一個空格分隔
投注組合本身必須按字典順序排列，也就是首先按最小的數字排序，然後是第二小的數字，依此類推

各測試案例之間必須以一個空行分隔
在最後一個測試案例之後不要輸出空行

解題思路

從大小為 k（6 < k < 13）的已排序集合 v 中，列舉所有可能的 6 個數字子集合 ans，並按字典序輸出

定義遞迴 f(x)，表示是否考慮選取 v[x]
在每個位置做「選取」與「不選取」兩種決策

終止條件：

• 當已選數字數量達 6 → 輸出一組解並返回
• 當已考慮完所有元素但未選滿 6 個 → 返回

因為輸入的數字為已排序陣列，所以結果也會按照字典序輸出

程式碼

#include <bits/stdc++.h>
using namespace std;

vector<int> v, ans;

void f(int x) {
    if (ans.size() == 6) { // 若 ans 陣列長度為 6，則進行輸出並終止
        for (auto &i : ans) cout << i << " \n"[&i == &ans.back()];
        return;
    }
    if (x == v.size()) return; // 若索引值超出 v 陣列的大小，就終止

    ans.push_back(v[x]); // 選擇 v[x]
    f(x+1); // 往下枚舉
    ans.pop_back(); // 不選擇
    f(x+1); // 往下枚舉
}

int main() {
    int n, T = 0;
    while (cin >> n, n) {
        if (T++) cout << '\n';
        v.assign(n, 0);
        for (auto &i : v) cin >> i;
        f(0);
    }
}