今天開始我們來講回溯演算法，聽名字好像很厲害，但其實也只是動態規劃問題的一種解法．

要使用回溯演算法，就是一個決策樹的尋訪過程．

而構成一個決策樹有以下幾個重點．

1.走過的路徑:到目前節點已經做出的選擇

2.選擇清單:接下來可以做出的選擇

3.結束條件:到達了決策樹的底層，無法做更多選擇的情況

大概的架構會像這樣

fun backTrack(路徑，選擇): 答案{
    if(滿足結束條件)
        return 答案
    for(選擇 in 可選擇列表){
        執行選擇 //重點
        backTrack(路徑,可選擇列表)
        撤銷選擇 //重點
    }       
}

直接看還是有點難懂，我們接下來用排列問題來解釋一下

排列問題

這個問題大家在高中應該遇到過，就是排列與組合的那

問題是這樣的: 有三個數字 [1,2,3] 把它們排成一列，請問有多少方法？

高中老師怎麼教的呢？

首先，數列第一位有三種選擇，所以先在算式上寫上 3

然後因為第一位已經固定了，第二位只剩下了兩個選擇 ，所以算式再乘以2

第三位，因為只剩下唯一一個選項了，所以就乘上1

最後結果，是3 * 2 * 1 = 6 ，總共有6種可能．

恩？好像有些關鍵字跟我們上面說的回溯演算法重複了．其實這種做法就是一種回溯演算法

讓我們把樹畫出來

(我知道很醜啦）

這棵樹我們稱之為決策樹，因為上面每個節點都在做決策．

比如說我們來看看這個被塗上色的節點

站在這個節點來看

1.走過的路徑:到目前節點已經做出的選擇
⇒已經做出選擇 “2”

2.選擇清單:接下來可以做出的選擇

⇒可以選擇 “1”或者”3”

3.結束條件:到達了決策樹的底層，無法做更多選擇的情況

⇒還沒有把所有數字都排列完，還能做選擇，所以沒有達到結束條件

我們來看看決策樹的一部分

前序的程式碼，在進入節點前執行，後序的程式碼，則是在離開某個節點後才行．

在我們於決策樹上面遍歷時，要維護節點的屬性正確，就要在這兩個時間點做做手腳．

所以，所謂的做選擇，就是從可選擇的清單中挑出一個選擇，放進路徑之中．而撤銷選擇，就是從路徑之中拿出一個選擇，放回可選擇的清單．

只要在遞迴前做出選擇，遞迴後撤銷選擇．就能夠維護好每個節點的可選擇清單以及路徑．
來看看程式碼吧

fun main(args: Array<String>) {
    var res: MutableList<List<Int>> = LinkedList<List<Int>>()
    val numbers = intArrayOf(1, 2, 3)

    fun backtrack(numbers: IntArray, track: LinkedList<Int>) {
        if(track.size == numbers.size){//全部數字都使用過 結束條件達成
            res.add(LinkedList(track))
            return
        }
        for(i in numbers.indices){
            if(track.contains(numbers[i])){//排除掉已經做過的選擇
                continue
            }
            track.add(numbers[i])//做選擇
            backtrack(numbers,track)//進入下一層決策
            track.removeLast()//撤銷選擇
        }
    }

    fun permute(numbers: IntArray): List<List<Int>> {
        val track: LinkedList<Int> = LinkedList<Int>()
        backtrack(numbers, track)
        return res
    }
    
    println(permute(numbers))
}

執行的結果如下