《啊哈！算法》第 4 章第 1 節(jié)牙寞，深度優(yōu)先搜索的 Swift 實現(xiàn)饺鹃。
問題
輸入一個數(shù) n，輸出 1～n 的全排列
解決
假設有編號 1间雀、2悔详、3 張紙牌，放入 1惹挟、2茄螃、3 號盒子中，每個盒子都按照 1连锯、2归苍、3 的順序依次嘗試。
let n = 3 //取值范圍從1～n
//下標 0 的位置沒有使用运怖，因此要初始化 n+1 項
var a = [Int](repeatElement(0, count: n+1)) //準備用來放數(shù)字的盒子
var book = [Int](repeatElement(0, count: n+1)) //記錄已放入的數(shù)字
func dfs(step: Int){
//如果站在 n+1 個盒子前拼弃，表示前 n 個盒子已經(jīng)放好數(shù)字
if step == n+1 {
//輸出一種排列
for i in 1...n {
print(a[i], separator: "", terminator: "")
}
print("\n")
return
}
//此時站在地 step 個盒子前
//按照1、2摇展、3……的順序一一嘗試
for i in 1...n {
// print("step: \(step), i: \(i)")
//判斷數(shù)字是否在手上吻氧，book[i]=0表示還未放置
if book[i] == 0 {
a[step] = i
book[i] = 1 //牌打出后設為1，表示牌不在手上了
//走到下一個盒子前，函數(shù)遞歸
dfs(step: step+1)
//把剛才嘗試的牌收回
book[i] = 0
}
}
}
dfs(step: 1)
代碼在 GitHub
