ZeroJudge 解題筆記：d115. 數字包牌

作者：王一哲
日期：2025年8月22日


ZeroJudge 題目連結：d115. 數字包牌

解題想法

這題通常是用自訂函式及遞迴，窮舉所有的組合。如果用 Python 解題，可以使用迭代器 itertools.combinations。這題的測資不太，看起來兩者效率差不多。

Python 程式碼

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

def solve(idx, arr, maxdepth, choose):
    if len(choose) + len(arr) - idx < maxdepth:  # 如果剩下的數字不夠用，跳出函式
        return
    if len(choose) == maxdepth:  # 如果 choose 長度等於 maxdepth，印出 choose
        print(*choose); return
    for i in range(idx, len(arr)):  # 依序讀取 arr[idx] ~ arr[-1]
        choose.append(arr[i])  # arr[i] 加入 choose
        solve(i+1, arr, maxdepth, choose)  # 遞迴，idx 改成 i+1
        choose.pop()  # 移除 choose 最後一筆資料

while True:  # 無窮迴圈
    line = list(map(int, input().split()))  # 讀取一行資料
    if len(line) == 1 and line[0] == 0: break  # 如果只有一個 0，中止迴圈
    n, m = line[0], line[-1]  # n 個數取 m 個
    arr = sorted(line[1:-1])  # 可用的數字
    solve(0, arr, m, [])  # 呼叫 solve 解題
    print("")  # 最後要換行

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

import sys
from itertools import combinations

result = []
lines = sys.stdin.readlines()
first_case = True
for line in lines:
    if not line.strip(): continue
    if line.strip() == "0": break
    if not first_case: result.append("\n")
    if first_case: first_case = False
    arr = list(map(int, line.split()))
    n = arr[0]
    nums = sorted(arr[1:1+n])
    m = arr[-1]
    for comb in combinations(nums, m):
        result.append(" ".join(map(str, comb)) + "\n")
sys.stdout.write("".join(result))

C++ 程式碼

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

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

void solve(int idx, vector<int>& arr, int maxdepth, vector<int>& choose) {
    // 如果剩下的數字不夠用，跳出函式
    if (choose.size() + arr.size() - (size_t)idx < (size_t)maxdepth) return;
    // 如果 choose 長度等於 maxdepth，印出 choose
    if (choose.size() == (size_t)maxdepth) {
        for(size_t i=0; i<choose.size(); i++) {
            printf("%d", choose[i]);
            if (i == choose.size()-1) printf("\n");
            else printf(" ");
        }
    }
    
    for(size_t i=idx; i<arr.size(); i++) {  // 依序讀取 arr[idx] ~ arr[-1]
        choose.push_back(arr[i]);  // arr[i] 加入 choose
        solve(i+1, arr, maxdepth, choose);  // 遞迴，idx 改成 i+1
        choose.pop_back();  // 移除 choose 最後一筆資料
    }
}

int main() {
    int n;  // n 個數字
    while(scanf("%d", &n) != EOF) {
        if (n == 0) break;  // 如果只有一個 0，中止迴圈
        vector<int> arr (n), choose;  // 可用的數字，選取的數字
        for(int i=0; i<n; i++) scanf("%d", &arr[i]);
        sort(arr.begin(), arr.end());  // 由小到大排序
        int m; scanf("%d", &m);  // n 個數取 m 個
        solve(0, arr, m, choose);  // 呼叫 solve 解題
        puts("");  // 最後要換行
    }
    return 0;
}