d653 - VAC+ _ 社費問題
題目描述
題目要求從 n 個數字中選出 m 個數字的所有組合，並輸出這些組合。輸入包含 n 和 m，以及 n 個數字。需要注意的是，數字可能未排序且可能重複，輸出時需要避免重複的組合，並且按照數字大小排序。
解題思路
這題可以使用回溯法 (Backtracking) 來解決。首先，對輸入的數字陣列進行排序，以便更容易地避免重複組合。然後，使用遞迴函式 dfs 來生成所有可能的組合。在遞迴過程中，我們從當前索引 it 開始，選擇一個數字加入到當前組合 ans 中，然後遞迴地選擇下一個數字。為了避免重複，我們在選擇數字時，跳過與前一個數字相同的數字。當組合中已經有 m 個數字時，輸出該組合。
複雜度分析
- 時間複雜度: O(C(n, m) * m)，其中 C(n, m) 代表從 n 個元素中選擇 m 個元素的組合數。在最壞情況下，需要生成所有可能的組合，並且對於每個組合，需要花費 O(m) 的時間來輸出。
- 空間複雜度: O(m)，主要用於儲存當前組合
ans。遞迴深度最大為 m，因此遞迴調用堆疊的空間複雜度也為 O(m)。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[105],ans[105];
void dfs(int it,int k){
if(k==m){
for(int j=0;j<m;++j){
cout << ans[j] << " ";
}
cout << "\n";
return;
}
else if(n-it<m-k){
return;
}
int la=-1;
for(int j=it;j<n;++j){
if(a[j]!=la){
ans[k]=a[j];
dfs(j+1,k+1);
la=a[j];
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cout.tie(0);
while(cin >> n >> m){
if(n==0&&m==0)break;
for(int i=0;i<n;++i){
cin >> a[i];
}
sort(a,a+n);
dfs(0,0);
}
}