一看就懂，一寫就懵？搞懂回溯算法，一口氣刷了20多道題

一、回溯算法

1.1什么是回溯？

回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。——摘自《百度百科》

1.1 一般步驟：

針對所給問題，定義問題的解空間，它至少包含問題的一個（最優）解。

確定易于搜索的解空間結構,使得能用回溯法方便地搜索整個解空間 。

以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效搜索。

1.2 如何理解回溯算法？

為問題建立解空間結構

在解空間結構上進行DFS搜索

設立回溯出口和剪枝點，減少無效搜索，出口處保存有效解.

1.3 解決那些問題？

組合問題：N個數??按?定規則找出k個數的集合

切割問題：?個字符串按?定規則有?種切割?式

?集問題：?個N個數的集合?有多少符合條件的?集

排列問題：N個數按?定規則全排列，有?種排列?式

棋盤問題：N皇后，解數獨等等。

1.4遞歸與回溯

首先先說明一下對遞歸 (Recursive)與回溯 (Backtrack)的理解。

1.4.1 遞歸 (Recursive)

程序調用自身的編程技巧稱為遞歸。

遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。 ——摘自《百度百科》

通常來說，為了描述問題的某一狀態，必須用到該狀態的上一個狀態；而如果要描述上一個狀態，又必須用到上一個狀態的上一個狀態…… 這樣用自己來定義自己的方法就是遞歸。

1.4.2. 回溯 (Backtrack)

回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。 ——摘自《百度百科》

在這種思想下，我們需要清晰的找出三個要素：選擇 (Options)，限制 (Restraints)，結束條件 (Termination)。

1.5.遞歸與回溯的區別

遞歸是一種算法結構。遞歸會出現在子程序中，形式上表現為直接或間接的自己調用自己。典型的例子是階乘，計算規律為：n!=n×(n?1)!n!=n \times (n-1)!，基本如下所示：

let fac = (n)=> { if(n == 1){ return n; }else{ return (n*fac(n - 1)); } }

回溯是一種算法思想，它是用遞歸實現的。回溯的過程類似于窮舉法，但回溯有“剪枝”功能，即自我判斷過程。

二、Leetcode回溯題目

2.1- 22. 括號生成

數字 n 代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括號組合。

示例 1：

輸入：n = 3 輸出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

輸入：n = 1 輸出：["()"]

提示：

1 <= n <= 8

思路分析

判斷左右括號所剩的數量，最初始都是n;當左括號（(）有剩余，繼續做選擇；

判斷當右括號比左括號剩的多，才能選右括號；繼續遞歸做選擇

出口:構建的字符串是 2n的時候，此時已經該分支已經構建完成，加入選項；

簡答繪制圖形

解題代碼

var generateParenthesis = function (n) { const res = []; const backTracing = (lRemain, rRemain, str) => { // 左右括號所剩的數量，str是當前構建的字符串 if (str.length == 2 * n) { // 字符串構建完成 res.push(str); // 加入解集 return; // 結束當前遞歸分支 } if (lRemain > 0) { // 只要左括號有剩，就可以選它，然后繼續做選擇（遞歸） backTracing(lRemain - 1, rRemain, str + "("); } if (lRemain < rRemain) { // 右括號比左括號剩的多，才能選右括號 backTracing(lRemain, rRemain - 1, str + ")"); // 然后繼續做選擇（遞歸） } }; backTracing(n, n, ""); // 遞歸的入口，剩余數量都是n，初始字符串是空串 return res; };

2.2 - 46. 全排列

給定一個不含重復數字的數組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：

輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1] 輸出：[[0,1],[1,0]]

示例 3：

輸入：nums = [1] 輸出：[[1]]

提示：

1 <= nums.length <= 6

-10 <= nums[i] <= 10

nums 中的所有整數 互不相同

解題思路

回溯終止條件：該條路徑長度與達到nums長度；

加入當前值到路徑，如果結果里面已經包含這個路徑，則不加入結果里面，否則繼續選擇這個選項；

解題代碼

/** * @param {number[]} nums * @return {number[][]} */ var permute = function (nums) { if (!nums.length) return let res = [] let backTrack = path => { //長度滿足條件，加入結果 if (path.length === nums.length) { res.push(path) return } nums.forEach(item => { if (path.includes(item)) return //不包含重復的數字 backTrack([...path, item]) //加入路徑，繼續遞歸選擇 }); } backTrack([]) return res };

[圖片上傳失敗…(image-40cdd5-1639281547994)]

2.3 - n 皇后問題

研究的是如何將 n 個皇后放置在 n × n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回 n 皇后問題 不同的解決方案的數量。***

皇后走法規則

皇后的走法是：可以橫直斜走，格數不限。因此要求皇后彼此之間不能相互攻擊，等價于要求任何兩個皇后都不能在同一行、同一列以及同一條斜線上。

示例

示例 1：

輸入：n = 4 輸出：2

解釋：如上圖所示，4 皇后問題存在兩個不同的解法。

示例 2：

輸入：n = 1 輸出：1

提示：

1 <= n <= 9

解題思路

定義判斷當前位置的檢驗函數，約束條件包含 ，不能同行，不能同列，不能同對角線（45度和135度）

定義棋盤；標準回溯處理；

使用回溯的具體做法是：依次在每一行放置一個皇后，每次新放置的皇后都不能和已經放置的皇后之間有攻擊，即新放置的皇后不能和任何一個已經放置的皇后在同一列以及同一條斜線上。當 NNN 個皇后都放置完畢，則找到一個可能的解，將可能的解的數量加 111。

圖片來源

解題代碼

var totalNQueens = function (n) { let count = 0; //皇后可放置的總數 let isValid = (row, col, board, n) => { //所在行不用判斷，每次都會下移一行 //判斷同一列的數據是否包含 for (let i = 0; i < row; i++) { if (board[i][col] === 'Q') { return false } } //判斷45度對角線是否包含 for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] === 'Q') { return false } } //判斷135度對角線是否包含 for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--) { if (board[i][j] === 'Q') { return false } } return true } let backTracing = (row, board) => { //走到最后一行，統計次數 if (row === n) { count++; return } for (let x = 0; x < n; x++) { //判斷該位置是否可以放置 皇后 if (isValid(row, x, board, n)) { board[row][x] = 'Q'; //放置皇后 backTracing(row + 1, board); //遞歸 board[row][x] = '.'; //回溯，撤銷處理結果 } } } backTracing(0, board) let board = [...Array(n)].map(v => v = ([...Array(n)]).fill('.')) //棋盤 return count };

2.4 - 78. 子集

給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。

解集 不能 包含重復的子集。你可以按 任意順序 返回解集。

示例 1：

輸入：nums = [1,2,3] 輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

輸入：nums = [0] 輸出：[[],[0]]

提示：

1 <= nums.length <= 10

-10 <= nums[i] <= 10

nums 中的所有元素 互不相同

解題思路

枚舉出所有可選的數；加入選項；

撤銷加入的選項，將選項加入結果

解題代碼

const subsets = (nums) => { const res = []; const backTracing = (index, list) => { res.push(list.slice()); // 調用子遞歸前，加入解集 for (let i = index; i < nums.length; i++) { // 枚舉出所有可選的數 list.push(nums[i]); // 選這個數 backTracing(i + 1, list); // 基于選這個數，繼續遞歸 list.pop(); // 撤銷選這個數 } }; backTracing(0, []); return res; };

2.5 - 77. 組合

給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。

你可以按 任何順序 返回答案。

示例 1：

輸入：n = 4, k = 2 輸出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

示例 2：

輸入：n = 1, k = 1 輸出：[[1]]

提示：

1 <= n <= 20

1 <= k <= n

解題思路

枚舉出所有可選的數；加入選項；

撤銷加入的選項，將選項加入結果

剪枝條件:選項的長度滿足條件；

解題代碼

/** * @param {number} n * @param {number} k * @return {number[][]} */ var combine = function (n, k) { let result = []; let backTracing = (start, path) => { // 如果已經選滿了的話，加入結果集中 if (path.length == k) { result.push(path.slice()); return; } // 從開始的數字到末尾的數字 for (let i = start; i <= n; i++) { // 加入選擇列表中 path.push(i); // 繼續深度搜索 backTracing(i + 1, path); // 撤銷選擇 path.pop(i); } }; backTracing(1, []); return result; };

2.6 - 081. 允許重復選擇元素的組合

給定一個無重復元素的正整數數組 candidates 和一個正整數 target ，找出 candidates 中所有可以使數字和為目標數 target 的唯一組合。

candidates 中的數字可以無限制重復被選取。如果至少一個所選數字數量不同，則兩種組合是唯一的。

對于給定的輸入，保證和為 target 的唯一組合數少于 150 個。

示例 1：

輸入: candidates = [2,3,6,7], target = 7 輸出: [[7],[2,2,3]]

示例 2：

輸入: candidates = [2,3,5], target = 8 輸出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

輸入: candidates = [2], target = 1 輸出: []

示例 4：

輸入: candidates = [1], target = 1 輸出: [[1]]

示例 5：

輸入: candidates = [1], target = 2 輸出: [[1,1]]

提示：

1 <= candidates.length <= 30

1 <= candidates[i] <= 200

candidate 中的每個元素都是獨一無二的。

1 <= target <= 500

解題思路

將當前元素加入到選項里面，并將計算結果，傳到選項，繼續遞歸；

當選項和大于目標值時，結束這個選項，直到找到符合的選項，并將選項加入結果；

解題代碼

var combinationSum = function (candidates, target) { const result = [], visited = []; backTracing(0, 0); return result; function backTracing(sum, cur) { if (target === sum) result.push(visited.slice()); if (target <= sum) return; for (let i = cur; i < candidates.length; i++) { visited.push(candidates[i]); //加入到選項里面 backTracing(sum + candidates[i], i);//選擇這個選項，繼續遞歸 visited.pop(); //插銷這個選擇 } } };

2.7 - 216. 組合總和 III

找出所有相加之和為 n 的 k 個數的組合。組合中只允許含有 1 - 9 的正整數，并且每種組合中不存在重復的數字。

說明：

所有數字都是正整數。

解集不能包含重復的組合。

示例 1:

輸入: k = 3, n = 7 輸出: [[1,2,4]]

示例 2:

輸入: k = 3, n = 9 輸出: [[1,2,6], [1,3,5], [2,3,4]]

解題思路

同組合1

解題代碼

var combinationSum3 = function (k, n) { let ans = []; let backTracing = (start, path) => { if (path.length === k && path.reduce((acc, prev) => acc += prev) === n) { ans.push(path.slice()) return } for (let i = start; i <= 9; i++) { path.push(i) backTracing(i + 1, path) path.pop(i) } } backTracing(1, []) return ans };

2.8 - 17. 電話號碼的字母組合

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

示例 1：

輸入：digits = "23" 輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

輸入：digits = "" 輸出：[]

示例 3：

輸入：digits = "2" 輸出：["a","b","c"]

提示：

0 <= digits.length <= 4

digits[i] 是范圍 [‘2’, ‘9’] 的一個數字。

解題思路

找到當前按鈕對應的字母字符串

拼接按鈕對應的字符串組合

選項滿足長度，加入結果

解題代碼

var letterCombinations = function (digits) { if(!digits.length) return [] const dic = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz', }, ans = []; let backTracing = (cur, index) => { if (index > digits.length - 1) { //選項滿足長度，加入結果 ans.push(cur) return } let curDic = dic[digits[index]] //找到當前按鈕對應的字母字符串 for (let prop of curDic) { backTracing(cur + prop,index+1) //拼接按鈕對應的字符串組合 } } backTracing('', 0) return ans };

2.9 - 08.01. 三步問題

三步問題。有個小孩正在上樓梯，樓梯有n階臺階，小孩一次可以上1階、2階或3階。實現一種方法，計算小孩有多少種上樓梯的方式。結果可能很大，你需要對結果模1000000007。

示例1:

輸入：n = 3 輸出：4 說明: 有四種走法

示例2:

輸入：n = 5 輸出：13

提示:

n范圍在[1, 1000000]之間

解題代碼(會超時)

var waysToStep = function (n) { let ans = [], map = [1, 2, 3] let backTracing = (path, sum) => { if (sum >= n) { if (sum == n) { ans++; } return } for (let i = 0; i < 3; i++) { path.push(map[i]); backTracing(path, sum + map[i]) path.pop(i) } } backTracing([], 0) return ans };

動態規劃解法

/** * @param {number} n * @return {number} */ var waysToStep = function (n) { let dp =[],mod = 1000000007; dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=4; for (let i = 4; i <= n; i++) { dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod } return dp[n] };

2-10 - 40. 組合總和 II

給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中只能使用一次。

注意：解集不能包含重復的組合。

示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8, 輸出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

示例 2:

輸入: candidates = [2,5,2,1,2], target = 5, 輸出: [ [1,2,2], [5] ]

提示:

1 <= candidates.length <= 100

1 <= candidates[i] <= 50

1 <= target <= 30

解題思路

思路同組合1

解題代碼

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum2 = function (candidates, target) { candidates.sort((a,b)=>a-b) let ans = []; let backTracing = (start, path, sum) => { if (sum >= target) { if (sum === target) { ans.push(path.slice()) } return } for (let i = start; i < candidates.length; i++) { if (i - 1 >= start && candidates[i - 1] == candidates[i]) { continue; } path.push(candidates[i]) backTracing(i + 1, path, sum + candidates[i]) path.pop() } } backTracing(0, [], 0) return ans };

2-11 - 47. 全排列 II

給定一個可包含重復數字的序列 nums ，按任意順序 返回所有不重復的全排列。

示例 1：

輸入：nums = [1,1,2] 輸出： [[1,1,2], [1,2,1], [2,1,1]]

示例 2：

輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8

-10 <= nums[i] <= 10

解題思路

同上全排列

解題代碼

var permuteUnique = function (nums) { let ans = []; let used = Array(nums.length).fill(false) let backTracing = (start, path) => { if (start === nums.length) { ans.push(path.slice()) return } for (let i = 0; i < nums.length; ++i) { if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) { continue; } path.push(nums[i]) used[i] = true backTracing(start + 1, path) used[i] = false path.pop() } } nums.sort((a, b) => a - b) backTracing(0, []) return ans };

三、總結

主要運用了回溯算法；而解決一個回溯問題，實際上就是一個決策樹的遍歷過程。

3.1 模板

let backtracking=(路徑，選擇列表) =>{ if (滿足結束條件)) { 存放路徑; return; } for (選擇：路徑，選擇列表) { 做出選擇； backtracking(路徑，選擇列表); // 遞歸 回溯，撤銷處理結果 } }

即:

1.路徑：也就是已經做出的選擇。

2.選擇列表：也就是你當前可以做的選擇。

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

3.2 剪枝函數

1.用約束條件剪除得不到的可行解的子樹

2.用目標函數剪取得不到的最優解的子樹

3.3 回溯法的一般步驟：

1.設置初始化的方案（給變量賦初始值，讀入已知數據等）

2.變換方式去試探，若全部試完側轉（7）

3.判斷此法是否成功（通過約束函數），不成功則轉（2）

4.試探成功則前進一步再試探

5.正確方案還是未找到則轉（2）

6.以找到一種方案則記錄并打印

7.退回一步（回溯），若未退到頭則轉（2）

8.已退到頭則結束或打印無解

繼續加油！！！

四、參考文獻

LeetCode 刷題筆記——遞歸與回溯的理解LeetCode 刷題筆記——遞歸與回溯的理解

圖解回溯算法圖解回溯算法

回溯算法總結回溯算法總結

Node.js Vue

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。