i646 - 排列組合-排列
題目描述
題目要求輸出所有長度為 N 的小寫字母排列，其中 N 的範圍是 1 到 7。排列的元素使用 'a', 'b', 'c' 等小寫字母，並且按照字典順序輸出所有可能的排列。輸入以 N=0 結束。
解題思路
這題可以使用遞迴的 Backtracking 演算法來解決。基本思路是維護一個 used 陣列，記錄每個字母是否已經被使用。遞迴函數 dfs 嘗試在每個位置填入一個尚未使用的字母。當所有位置都填滿時，輸出當前的排列。為了確保輸出按照字典順序，在遞迴過程中，我們按照字母的順序嘗試填入每個位置。
複雜度分析
- 時間複雜度: O(n!)，其中 n 是輸入的整數 N。因為需要生成所有可能的排列，排列的數量是 n!。
- 空間複雜度: O(n)，主要用於儲存
a陣列和used陣列。遞迴深度也是 O(n)。
程式碼
#include <iostream>
using namespace std;
int a[8],n;
bool used[8];
void dfs(int x,int y){
if(y==n){
for(int i=0;i<n;++i)
cout << (char)(a[i]+'a');
cout << "\n";
return;
}
for(int i=0;i<n;++i)
if(!used[i]){
used[i]=1;
a[y]=i;
dfs(i+1,y+1);
used[i]=0;
}
}
int main(){
while(cin >> n){
if(n==0)break;
for(int i=0;i<n;++i){
used[i]=1;
a[0]=i;
dfs(i+1,1);
used[i]=0;
}
}
}