ZeroJudge 解題筆記：c074. 00441 - Lotto

作者：王一哲
日期：2026年2月16日


ZeroJudge 題目連結：c074. 00441 - Lotto

解題想法

這題可以用遞迴窮舉所有的組合。但如果用 Python 解題，可以用 itertools.combinations 枚舉所有指定數據中取出 6 個的組合，速度比遞迴還快。

Python 程式碼

使用時間約為 9 ms，記憶體約為 3.1 MB，通過測試。

import sys

def solve(cand, arr, depth):
    if len(arr) == depth:
        print(*arr)
        return
    for i in range(len(cand)):
        arr.append(cand[i])
        solve(cand[i+1:], arr, depth)
        arr.pop()
        
first = True
for line in sys.stdin:
    if line.rstrip() == "0": break
    if not first: print()
    first = False
    nums = list(map(int, line.split()))[1:]
    solve(nums, [], 6)

使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

import sys
from itertools import combinations

result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    n = int(data[ptr])
    ptr += 1
    if n == 0: break
    nums = sorted(map(int, data[ptr:ptr+n]))
    ptr += n
    if result: result.append("\n")
    for comb in combinations(nums, 6):
        res = " ".join(map(str, comb))
        result.append(f"{res}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 300 kB，通過測試。

#include <cstdio>
#include <vector>
using namespace std;

void solve(vector<int>& cand, vector<int>& arr, int depth) {
    if ((int)arr.size() == depth) {
        for(int i=0; i<depth-1; i++) printf("%d ", arr[i]);
        printf("%d\n", arr[depth-1]);
        return;
    }
    for(int i=0; i<(int)cand.size(); i++) {
        arr.push_back(cand[i]);
        vector<int> sub (cand.begin()+i+1, cand.end());
        solve(sub, arr, depth);
        arr.pop_back();
    }
}

int main() {
    bool first = true;
    int k;
    while(scanf("%d", &k) != EOF && k != 0) {
        if (!first) puts("");
        first = false;
        vector<int> nums (k), arr;
        for(int i=0; i<k; i++) scanf("%d", &nums[i]);
        solve(nums, arr, 6);
    }
    return 0;
}