這篇我們要介紹 LeetCode 題目常見會運用到的演算法，也就是 Backstracking ，翻譯成中文叫做回溯演算法，這個演算法著重在會列舉所有的可能性，因此也算是一個暴力解法，如果有其他解法，就不要使用，因為時間複雜度會快速增長。多半的題型會是屬於排列跟組合。(筆者的數學惡夢！) 而最經典的題目是八皇后或是數獨。

回溯程式碼

在程式碼的作法會是利用遞迴往下尋找並且建立各種組合，在過程中按照題目條件除去不需要的組合，所以它的程式碼結構多半會是長這個樣子。

func backtracking(参数) {
    if (停止的條件) {
        儲存結果
        return
    }

    for (選擇元素：本層集合中元素) {
        處理節點
        backtracking(路徑，選擇元素)
        回溯，刪除加入的節點
    }
}

如果畫出走訪回溯的圖範例，則會像是樹一樣列舉出各種結果，針對我們需要的做樹的刪減。

讓我們來看 LeetCode 題目 46. Permutations。

題目會給我們不重複的數字陣列，需要回覆各種可能排列的陣列，這些陣列們可不用順序排列。

範例一

輸入: nums = [1,2,3]
輸出結果: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

範例二

輸入: nums = [0,1]
輸出結果: [[0,1],[1,0]]

更多範例跟邊際說明可以點選 LeetCode 網站觀看題目，這邊主要看範例一，我們針對 [1, 2, 3] 去畫樹狀圖，一個一個組起來我們需要的結果。

再一個一個組成可能性陣列的過程中，我們會去判斷是否有沒有重複，如果重複了就不是我們要的結果，就不繼續進行往下查找的動作，並且回彈會上一個樹節點。

Swift 程式碼會長的如下：

class Solution {
    // 結果陣列
    var res = [[Int]]()
    
    func permute(_ nums: [Int]) -> [[Int]] {
        var tmp = [Int]()
        backtracking(nums, &tmp)
        return res
    }
    
    func backtracking(_ nums: [Int], _ tmp: inout [Int]) {
				// 判斷蒐集數字的陣列已經跟 nums 陣列一樣大小表示達到停止條件，可結束
        if tmp.count == nums.count {
	          // 儲存收集到的結果陣列
            res.append(tmp)
            return
        }
        
        for i in 0..<nums.count {
            // 判斷數字重複則不往下查找收集
            if tmp.contains(nums[i]) { continue }
            // 回溯演算法查找並蒐集數字
            tmp.append(nums[i])
            backtracking(nums, &tmp)
            tmp.removeLast()
        }
    }
}

時間複雜度：時間複雜度約為 O(n!)，因為有各種排列

空間複雜度：tmp 是 O(n) 而 res 是 O(n!)，加總起來是 O(n+n!)

總結

這個演算法如果有了解它的概念，表示已經跨越一大步，這類型題目多半難度是 Medium，因為遞迴加上要判斷停止條件，還有減少不需要的走訪條件，能夠想出來都不容易，學會這題後，可以去挑戰更經典的八皇后題目，希望大家在刷題的路上都能夠順利。

更多資料可以參考如下網站，幫助概念理解很多，會比直接寫題目卡關還更有效率。

• Backtracking 回溯
• 一次看懂遞迴(Recursion) 的思維模式（三）