&emsp;&emsp;回溯算法（backtracking）是一個類似枚舉的搜索嘗試過程，在尋找問題解的過程中，當發現不滿足求解條件時，就退回一步，嘗試其它路徑，該算法的時間復雜度都不會低于 O(N!)，復雜的例題包括[正則表達式匹配](https://leetcode-cn.com/problems/regular-expression-matching/)、[解數獨](https://leetcode-cn.com/problems/sudoku-solver/)等。 &emsp;&emsp;在《[回溯算法詳解](https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban)》一文中提到，解決一個回溯問題，實際上就是一個決策樹的遍歷過程，需要思考三個問題： &emsp;&emsp;（1）路徑：已經做出的選擇。 &emsp;&emsp;（2）選擇列表：當前可以做的選擇。 &emsp;&emsp;（3）結束條件：到達決策樹底層，無法再做選擇的條件。 &emsp;&emsp;下面是改編過的算法通用結構。 ~~~ function backtrack(路徑, 選擇列表): if 滿足結束條件 console.log(路徑) return for 選擇 of 選擇列表 做選擇 backtrack(路徑, 選擇列表) 撤銷選擇 ~~~ &emsp;&emsp;面試題12[矩陣路徑](https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/)和面試題13[機器人運動范圍](https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/)。在二維方格或矩陣的運動可用回溯法解決。 ## 一、N皇后 &emsp;&emsp;[N皇后](https://leetcode-cn.com/problems/n-queens/)是一道經典的回溯算法題，將 n 個皇后放置在 n×n 的棋盤上，使皇后彼此之間不能相互攻擊，即每個棋子所在的行、列、對角線都不能有另一個棋子。 &emsp;&emsp;在下面的[示例](https://codepen.io/strick/pen/JjGzMed)中，N是皇后的數量，backtrack()函數是回溯過程（如下所列），isValid()函數判斷是否符合選中條件。 &emsp;&emsp;（1）從第一個 row=0 開始。 &emsp;&emsp;（2）循環列并且試圖在每個 column 中放置皇后。 &emsp;&emsp;（3）如果方格 (row, column) 在攻擊范圍內，那么跳過。 &emsp;&emsp;（4）在 (row, column) 方格上放置皇后，繼續尋找下一個位置。 &emsp;&emsp;（5）判斷 row 是否和皇后數量相同。 ~~~ const N = 4; function backtrack(route, row) { if (row == N) { //結束條件 console.log(route); return; } for (let column = 0; column < N; column++) { if (!isValid(route, row, column)) continue; route[row] = column; //做選擇 backtrack(route, row + 1); //下一步 route[row] = null; //撤銷選擇（可省略） } } //從下往上 判斷row行column列放置是否合適 function isValid(route, row, column) { let leftup = column - 1, rightup = column + 1; for (let i = row - 1; i >= 0; i--) { // 逐行往上考察每一行 if (route[i] == column) // 第i行的column列有棋子 return false; if (leftup >= 0) { if (route[i] == leftup) // 考察左上對角線：第i行leftup列有棋子 return false; } if (rightup < N) { if (route[i] == rightup) // 考察右上對角線：第i行rightup列有棋子 return false; } leftup--; rightup++; } return true; } ~~~ ## 二、0-1背包 &emsp;&emsp;有一個背包，背包總的承載重量是 Wkg。現在有 n 個物品，假設每個物品的重量都不相等，并且不可分割。期望選擇幾件物品，裝載到背包中。在不超過背包容量的前提下，如何讓背包中物品的總重量最大？ &emsp;&emsp;把物品依次排列，對于物品選擇裝或不裝，然后遞歸余下的物品，[如下所示](https://codepen.io/strick/pen/dyGrmzw)。 ~~~ let max = Number.MIN_VALUE, W = 100; function backtrack(route, goods) { let weight = route.length ? route.reduce((acc, cur) => acc += cur) : 0; if (weight == W || route.length == goods.length) { //結束條件 if (weight > max && weight <= W) { max = weight; } console.log(route); return; } for (let i = 0; i < goods.length; i++) { if(weight + goods[i] > W || route.indexOf(goods[i]) > -1) continue; route.push(goods[i]); //做選擇 backtrack(route, goods); route.pop(); //撤銷選擇 } } ~~~ ## 三、全排列 &emsp;&emsp;[全排列](https://leetcode-cn.com/problems/permutations/)是指輸出給定數字序列的全部可能的排列，假設序列中的數字都是唯一的，利用回溯算法枚舉出所有排列，[如下所示](https://codepen.io/strick/pen/VweNBKd)。 ~~~ function backtrack(route, nums) { if (route.length == nums.length) { //結束條件 console.log(route); return; } for (let i = 0; i < nums.length; i++) { if (route.indexOf(nums[i]) > -1) continue; route.push(nums[i]); //做選擇 backtrack(route, nums); route.pop(); //撤銷選擇 } } ~~~ &emsp;&emsp;面試題17[打印從 1~n 位的數](https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/)。將問題轉換成數字排列，用遞歸實現。 ***** > 原文出處： [博客園-數據結構和算法躬行記](https://www.cnblogs.com/strick/category/1809992.html) 已建立一個微信前端交流群，如要進群，請先加微信號freedom20180706或掃描下面的二維碼，請求中需注明“看云加群”，在通過請求后就會把你拉進來。還搜集整理了一套[面試資料](https://github.com/pwstrick/daily)，歡迎閱讀。  推薦一款前端監控腳本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不僅能監控前端的錯誤、通信、打印等行為，還能計算各類性能參數，包括 FMP、LCP、FP 等。