問題：全排列的種樹是N!气堕，要求按字典序輸出流纹。
思路：我們可以把N個(gè)數(shù)兩兩建立無向邊（即任意兩個(gè)結(jié)點(diǎn)之間都有邊拆挥，也就是一個(gè)N個(gè)結(jié)點(diǎn)的完全圖）薄霜，然后對(duì)每個(gè)點(diǎn)作為起點(diǎn)，分別做一次深度優(yōu)先遍歷纸兔，當(dāng)所有點(diǎn)都已經(jīng)標(biāo)記時(shí)輸出當(dāng)前的遍歷路徑惰瓜，就是其中一個(gè)排列，這里需要注意汉矿，回溯的時(shí)候需要將原先標(biāo)記的點(diǎn)的標(biāo)記取消崎坊，否則只能輸出一個(gè)排列。如果要按照字典序洲拇，則需要在遍歷的時(shí)候保證每次遍歷都是按照結(jié)點(diǎn)從小到大的方式進(jìn)行遍歷的奈揍。
image.png
代碼：
#include <iostream>
using namespace std;
void dfs(int arr[],int n,int visited[],int i,int out[])
{
if(i == n)
{
for (int j = 0; j < n; ++j) {
cout<<out[j]<<" ";
}
cout<<endl;
} else{
for (int j = 0; j < n; ++j) {
if (visited[j] == 0)
{
out[i] = arr[j];
visited[j] = 1;
dfs(arr,n,visited,i+1,out);
visited[j] = 0;
}
}
}
}
int test_FullAranged()
{
//freopen("in.txt","r",stdin);
int n = 5;
int arr[5] = {1,2,3,4,5};
int visited[5];
memset(visited,0, sizeof(visited));
int out[5];
dfs(arr,n,visited,0,out);
}
