d597 - 2. 便當的編號與配菜組合
題目描述
題目要求計算給定配菜組合的便當編號，並輸出下一個配菜組合。如果輸入的配菜組合是最後一個，則輸出 "no next combination"。
解題思路
程式使用深度優先搜尋 (DFS) 產生所有可能的配菜組合，並按照字典順序排列。程式首先讀取 n 和 k，然後讀取給定的配菜組合 a。DFS 函數 dfs 遞迴地產生所有可能的組合，並計算當前組合的編號。當找到與輸入組合相同的組合時，記錄其編號 fd。然後，程式繼續搜尋下一個組合，並將其儲存在 ans 陣列中。如果找到下一個組合，則輸出其編號和組合。否則，輸出 "no next combination"。
複雜度分析
- 時間複雜度: O(C(n, k))，其中 C(n, k) 是從 n 個元素中選取 k 個元素的組合數。因為程式需要產生所有可能的組合。
- 空間複雜度: O(k)，因為程式需要儲存當前組合和下一個組合，每個組合的大小為 k。
程式碼
#include <iostream>
using namespace std;
int a[11],n,k,tmp[11],t2[11],count,fd,ans[11];
void dfs(int it,int w){
t2[w]=tmp[it];
if(w==k-1){
++count;
int ch=1;
for(int i=0;i<k;++i)
if(a[i]!=t2[i])ch=0;
if(ch)
fd=count;
if(fd&&count==fd+1)
for(int i=0;i<k;++i)
ans[i]=t2[i];
return;
}
for(int i=it+1;i<n;++i){
dfs(i,w+1);
}
}
int main(){
cin >> n >> k;
for(int i=0;i<n;++i)
tmp[i]=i+1;
for(int i=0;i<k;++i)
cin >> a[i];
for(int i=0;i<n;++i)
dfs(i,0);
cout << fd << "\n";
if(fd==count)
cout << "no next combination";
else
for(int i=0;i<k;++i)
cout << ans[i] << " ";
}