i645 - 排列組合-組合

🔗 前往 ZeroJudge 原題

題目描述

題目要求從 N 個物件中取出 M 個物件的所有組合，並按照字典順序輸出。物件的代號使用小寫字母 a, b, c,... 表示。輸入包含多組測試資料，直到 N 和 M 都為 0 時結束。

解題思路

此題可以使用遞迴的 backtracking 演算法來產生所有組合。dfs 函數負責遞迴地選擇物件。x 參數表示當前可以選擇的起始索引，y 參數表示已經選擇了多少個物件。當 y 等於 m 時，表示已經選擇了足夠數量的物件，輸出當前組合。在遞迴過程中，從 x 開始遍歷所有可能的物件，將物件加入當前組合，然後遞迴地選擇下一個物件。

複雜度分析

• 時間複雜度: O(C(n, m) * m)，其中 C(n, m) 是從 n 個物件中選擇 m 個物件的組合數。因為需要產生所有組合，並且每個組合的輸出需要 O(m) 的時間。
• 空間複雜度: O(m)，主要用於儲存當前組合。遞迴深度最大為 m。

程式碼

#include <iostream>
using namespace std;
int a[11],ct,n,m;
void dfs(int x,int y){
	if(y==m){
		for(int i=0;i<m;++i)
			cout << (char)(a[i]+'a');
		cout << "\n";
		return;
	}
	for(int i=x;i<n;++i){
		a[y]=i;
		dfs(i+1,y+1);
	}
}
int main(){
	while(cin >> n >> m){
		if(n==0&&m==0)break;
		for(int i=0;i<=n-m;++i){
			a[0]=i;
			dfs(i+1,1);
		}
	}
}