原文鏈接
DFS解決全排列問(wèn)題驶沼，從一道奧數(shù)題開(kāi)始說(shuō)起。http://www.reibang.com/p/897f2a9e33cd
總結(jié)
有關(guān)全排列的題目可以通過(guò)DFS來(lái)解決争群。
- 最簡(jiǎn)單的例子
- 題目：有數(shù)字1-9，求其全排列
- 分析：
想象有九個(gè)空位a[9]大年，現(xiàn)在第一個(gè)空位上填上一個(gè)數(shù)字换薄，有多種選擇玉雾，假設(shè)a[0] = 1；
接下來(lái)在第二個(gè)空位上繼續(xù)填數(shù)字轻要，要求不與之前填過(guò)的數(shù)字相同（用book標(biāo)記）复旬，則還剩下8個(gè)數(shù)字可以選擇，假設(shè)a[1] = 2冲泥；
依次類推驹碍，全部填滿，打印凡恍。
之后要退回一位志秃，恢復(fù)book標(biāo)記，選擇其他數(shù)字嚼酝，向下填空浮还。 - 偽代碼
void dfs(int step){ //step表示當(dāng)前要處理的盒子
if(step == n+1){
//輸出排列
for(i = 1; i <= n; i++)
printf("%d", a[i]);
printf("\n");
return;
}
for(int i = 1; i <= n; i++){
if(book[i] == 0){
a[step] = i; //將i放入第step個(gè)空位
book[i] = 1; // i已經(jīng)被使用了
dfs(step+1); //向下調(diào)用
book[i] = 0; // 非常重要，收回該空位中的數(shù)字才能進(jìn)行下一次嘗試闽巩。
}
}
}
- DFS框架
由上述分析钧舌，可發(fā)現(xiàn)過(guò)程類似DFS框架。DFS核心在于涎跨，對(duì)于每一個(gè)中可能性都嘗試一遍洼冻，確定當(dāng)前位的數(shù)字后，再以同樣的方式調(diào)用下一位隅很。
偽代碼：
void dfs(int step){
*判斷結(jié)束邊界*
嘗試每一種可能 for(i = 1; i <= n; i++){
嘗試下一步 dfs(step + 1);
}
return;
}
- 其他變形
- 判斷每一種可能——給定數(shù)組撞牢，空位選擇不重復(fù)
1-9可能變形為給定數(shù)組，則同樣可以通過(guò)索引和book來(lái)選擇數(shù)據(jù)外构；此外普泡，還可以用swap來(lái)代替book，對(duì)于給定數(shù)組审编，在指定位可以與后面的數(shù)字交換撼班，同樣可以實(shí)現(xiàn)選擇的功能。
例子： [http://blog.csdn.net/ns_code/article/details/26509459 - 重復(fù)數(shù)組中有重復(fù)的垒酬，求不同的排列
額外開(kāi)啟一個(gè)unsorted_set用于記錄當(dāng)前位已經(jīng)選擇過(guò)的數(shù)字砰嘁，如果再次遇到已經(jīng)選擇過(guò)的數(shù)字，則跳過(guò)勘究。
- 判斷每一種可能——給定數(shù)組撞牢，空位選擇不重復(fù)
