定義

? 回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。許多復(fù)雜的，規(guī)模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。
?

回溯法：一種通過探索所有可能的候選解來找出所有的解的算法。如果候選解被確認不是一個解的話（或者至少不是最后一個解），回溯算法會通過在上一步進行一些變化拋棄該解，即回溯并且再次嘗試。

回溯問題，實際上就是決策樹的遍歷過程。

? 需要思考 3 個問題：

路徑：也就是已經(jīng)做出的選擇。

選擇列表：也就是你當(dāng)前可以做的選擇。

結(jié)束條件：也就是到達決策樹底層，無法再做選擇的條件。

?

• 回溯算法的框架技巧

result = [] function backtrack(選擇列表, 路徑){if 滿足結(jié)束條件 {result.add(路徑)return}for 選擇 of 選擇列表 {做選擇入棧backtrack(選擇列表, 路徑)撤銷選擇出棧，繼續(xù)下一輪} } ? 其核心就是 for 循環(huán)里面的遞歸，在遞歸調(diào)用之前「做選擇」，在遞歸調(diào)用之后「撤銷選擇」。
?

【46】全排列

思路

全排列窮舉，以開頭為索引起點，遞歸列舉每個起點開始的所有排列情況，遇到自己則忽略，按照以上的技巧來答題；

具體來說就是執(zhí)行一次深度優(yōu)先遍歷，從樹的根結(jié)點到葉子結(jié)點形成的路徑就是一個全排列。

題解

//給定一個 沒有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。 // // 示例: // // 輸入: [1,2,3] //輸出: //[ // [1,2,3], // [1,3,2], // [2,1,3], // [2,3,1], // [3,1,2], // [3,2,1] //] // Related Topics 回溯算法 //leetcode submit region begin(Prohibit modification and deletion) /*** @param {number[]} nums* @return {number[][]}*/ var permute = function (nums) {if (!nums || nums.length === 0) return [];if (nums.length <= 1) return [nums];// 路徑：記錄在 track 中var backtrack = function (nums, track = [], result) {// 結(jié)束條件：nums 中的元素全都在 track 中出現(xiàn)if (track.length === nums.length) {// 推入結(jié)果集，復(fù)制當(dāng)前數(shù)組并跳出result.push(track.slice(0));return;}for (var i = 0; i < nums.length; i++) {// 排除不合法的選擇if (track.includes(nums[i])) continue;track.push(nums[i]);// 進入下一層決策樹backtrack(nums, track);// 尾數(shù)出棧，繼續(xù)當(dāng)前遍歷track.pop();}};var result = [],track = [];backtrack(nums, track, result);return result; };

復(fù)雜度分析

時間復(fù)雜度：O(n * n!)，其中 n 為序列的長度。

空間復(fù)雜度：O(n)，其中 n 為序列的長度。除答案數(shù)組以外，遞歸函數(shù)在遞歸過程中需要為每一層遞歸函數(shù)分配棧空間，所以這里需要額外的空間且該空間取決于遞歸的深度，這里可知遞歸調(diào)用深度為 O(n)。

【47】全排列 II

思路

這道題是上題的變體，增加了可重復(fù)數(shù)字的排列，因此再全排列過程中需要進行剪枝去重；

剪枝的前提條件便是：當(dāng)前索引的值是否已經(jīng)入棧；當(dāng)前索引值與前一個索引值相等并且已經(jīng)使用過則跳過，此條件需要序列進行前置排序，不然就無法匹配到相鄰的重復(fù)值了；

題解

//給定一個可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。 // // 示例: // // 輸入: [1,1,2] //輸出: //[ // [1,1,2], // [1,2,1], // [2,1,1] //] // Related Topics 回溯算法//leetcode submit region begin(Prohibit modification and deletion) /*** @param {number[]} nums* @return {number[][]}*/ var permuteUnique = function (nums) {if (!nums || nums.length === 0) return [];if (nums.length <= 1) return [nums];var result = [],track = [],used = {};// 排序是剪枝的必要操作// 為了判斷相鄰的重復(fù)數(shù)據(jù)是否達到剪枝條件nums.sort();var backtrack = function (nums, track, used, depth) {if (depth === nums.length) {// 符合規(guī)則的數(shù)組入棧result.push(track.slice(0));return;}for (var i = 0; i < nums.length; i++) {// 使用過則跳出if (used[i]) continue;// 剪枝 保證 nums[i - 1] 有意義if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;track.push(nums[i]);// 標(biāo)記索引 i 使用過used[i] = true;// 遞歸排列backtrack(nums, track, used, depth + 1);// 標(biāo)記使用完畢used[i] = false;// 出棧，繼續(xù)循環(huán)排列track.pop();}};backtrack(nums, track, used, 0);return result; }; //leetcode submit region end(Prohibit modification and deletion)

復(fù)雜度

時間復(fù)雜度：O(n * n!)，這里 n 為數(shù)組的長度。

空間復(fù)雜度：O(n * n!)。

閑來刷下「回溯算法」 - 掘金?juejin.im

總結(jié)

以上是生活随笔為你收集整理的回溯法遵循深度优先吗_闲来刷下「回溯算法」的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。