ZeroJudge 解題筆記：i645. 排列組合-組合

作者：王一哲
日期：2025年11月20日


ZeroJudge 題目連結：i645. 排列組合-組合

解題想法

這題原來應該是要考用函式遞迴及回溯，但是在 Python 可以用 itertools.combinations 産生所有的組合。

Python 程式碼

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

import sys

def comb(n, m, start, s):
    if len(s) == m:
        print(s)
        return 
    for i in range(start, n):
        c = chr(i + ord('a'))
        comb(n, m, i+1, s+c)

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    comb(n, m, 0, "")

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

import sys
from itertools import combinations

result = []
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    chars = [chr(i + ord('a')) for i in range(n)]
    for comb in combinations(chars, m):
        s = "".join(comb)
        result.append(f"{s}\n")
sys.stdout.write("".join(result))

C++ 程式碼

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

#include <iostream>
#include <string>
using namespace std;

void comb(int n, int m, int start, string s) {
    if ((int)s.size() == m) {
        cout << s << "\n";
        return;
    }
    for(int i=start; i<n; i++) {
        char c = char(i + 'a');
        comb(n, m, i+1, s+c);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    while(cin >> n >> m) {
        if (n == 0 && m == 0) break;
        string s = "";
        comb(n, m, 0, s);
    }
    return 0;
}