攝影風春運祝福公眾號首圖@凡科快圖.png
一、回溯算法
1.1什么是回溯秧廉？
回溯算法實際上一個類似枚舉的搜索嘗試過程伞广，主要是在搜索嘗試過程中尋找問題的解，當發(fā)現(xiàn)已不滿足求解條件時疼电，就“回溯”返回赔癌，嘗試別的路徑±焦担——摘自《百度百科》
image
1.1 一般步驟：
- 針對所給問題灾票，定義問題的解空間，它至少包含問題的一個（最優(yōu)）解茫虽。
- 確定易于搜索的解空間結(jié)構(gòu),使得能用回溯法方便地搜索整個解空間 刊苍。
- 以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索濒析。
1.2 如何理解回溯算法正什？
- 為問題建立解空間結(jié)構(gòu)
- 在解空間結(jié)構(gòu)上進行DFS搜索
- 設立回溯出口和剪枝點，減少無效搜索号杏，出口處保存有效解.
1.3 解決那些問題婴氮？
- 組合問題：N個數(shù)??按?定規(guī)則找出k個數(shù)的集合
- 切割問題：?個字符串按?定規(guī)則有?種切割?式
- ?集問題：?個N個數(shù)的集合?有多少符合條件的?集
- 排列問題：N個數(shù)按?定規(guī)則全排列，有?種排列?式
- 棋盤問題：N皇后盾致，解數(shù)獨等等主经。
1.4遞歸與回溯
首先先說明一下對遞歸 (Recursive)與回溯 (Backtrack)的理解。
1.4.1 遞歸 (Recursive)
程序調(diào)用自身的編程技巧稱為遞歸庭惜。
遞歸做為一種算法在程序設計語言中廣泛應用罩驻。 一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解护赊，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算惠遏，大大地減少了程序的代碼量。 ——摘自《百度百科》
通常來說骏啰，為了描述問題的某一狀態(tài)节吮，必須用到該狀態(tài)的上一個狀態(tài)；而如果要描述上一個狀態(tài)判耕，又必須用到上一個狀態(tài)的上一個狀態(tài)…… 這樣用自己來定義自己的方法就是遞歸透绩。
1.4.2. 回溯 (Backtrack)
回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發(fā)現(xiàn)已不滿足求解條件時渺贤，就“回溯”返回雏胃，嘗試別的路徑请毛。 ——摘自《百度百科》
在這種思想下志鞍，我們需要清晰的找出三個要素：選擇 (Options)，限制 (Restraints)方仿，結(jié)束條件 (Termination)固棚。
image
1.5.遞歸與回溯的區(qū)別
遞歸是一種算法結(jié)構(gòu)。遞歸會出現(xiàn)在子程序中仙蚜，形式上表現(xiàn)為直接或間接的自己調(diào)用自己此洲。典型的例子是階乘，計算規(guī)律為：n!=n×(n?1)!n!=n \times (n-1)!委粉，基本如下所示：
let fac = (n)=> {
if(n == 1){
return n;
}else{
return (n*fac(n - 1));
}
}
回溯是一種算法思想呜师，它是用遞歸實現(xiàn)的〖纸冢回溯的過程類似于窮舉法汁汗，但回溯有“剪枝”功能，即自我判斷過程栗涂。
二知牌、Leetcode回溯題目
2.1- 22. 括號生成
數(shù)字 n 代表生成括號的對數(shù)，請你設計一個函數(shù)斤程，用于能夠生成所有可能的并且 有效的 括號組合角寸。
示例 1：
輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
輸入：n = 1
輸出：["()"]
提示：
1 <= n <= 8
思路分析
- 判斷左右括號所剩的數(shù)量，最初始都是n;當左括號（(）有剩余忿墅，繼續(xù)做選擇扁藕；
- 判斷當右括號比左括號剩的多，才能選右括號疚脐；繼續(xù)遞歸做選擇
- 出口:構(gòu)建的字符串是 2n的時候纹磺，此時已經(jīng)該分支已經(jīng)構(gòu)建完成，加入選項亮曹；
簡答繪制圖形
image
解題代碼
var generateParenthesis = function (n) {
const res = [];
const backTracing = (lRemain, rRemain, str) => { // 左右括號所剩的數(shù)量橄杨，str是當前構(gòu)建的字符串
if (str.length == 2 * n) { // 字符串構(gòu)建完成
res.push(str); // 加入解集
return; // 結(jié)束當前遞歸分支
}
if (lRemain > 0) { // 只要左括號有剩，就可以選它照卦，然后繼續(xù)做選擇（遞歸）
backTracing(lRemain - 1, rRemain, str + "(");
}
if (lRemain < rRemain) { // 右括號比左括號剩的多式矫，才能選右括號
backTracing(lRemain, rRemain - 1, str + ")"); // 然后繼續(xù)做選擇（遞歸）
}
};
backTracing(n, n, ""); // 遞歸的入口，剩余數(shù)量都是n役耕，初始字符串是空串
return res;
};
2.2 - 46. 全排列
給定一個不含重復數(shù)字的數(shù)組 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 中的所有整數(shù) 互不相同
解題思路
- 回溯終止條件：該條路徑長度與達到nums長度故慈；
- 加入當前值到路徑板熊，如果結(jié)果里面已經(jīng)包含這個路徑，則不加入結(jié)果里面察绷，否則繼續(xù)選擇這個選項干签；
image
解題代碼
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
if (!nums.length) return
let res = []
let backTrack = path => {
//長度滿足條件，加入結(jié)果
if (path.length === nums.length) {
res.push(path)
return
}
nums.forEach(item => {
if (path.includes(item)) return //不包含重復的數(shù)字
backTrack([...path, item]) //加入路徑拆撼，繼續(xù)遞歸選擇
});
}
backTrack([])
return res
};
[圖片上傳失敗...(image-40cdd5-1639281547994)]
2.3 - n 皇后問題
研究的是如何將 n 個皇后放置在 n × n 的棋盤上容劳，并且使皇后彼此之間不能相互攻擊。
給你一個整數(shù) n 闸度，返回 n 皇后問題 不同的解決方案的數(shù)量竭贩。***
image
皇后走法規(guī)則
皇后的走法是：可以橫直斜走，格數(shù)不限莺禁。因此要求皇后彼此之間不能相互攻擊留量，等價于要求任何兩個皇后都不能在同一行、同一列以及同一條斜線上哟冬。
示例
示例 1：
image
輸入：n = 4
輸出：2
解釋：如上圖所示楼熄，4 皇后問題存在兩個不同的解法。
示例 2：
輸入：n = 1
輸出：1
提示：
1 <= n <= 9
解題思路
- 定義判斷當前位置的檢驗函數(shù)柒傻，約束條件包含 孝赫，不能同行，不能同列红符，不能同對角線（45度和135度）
- 定義棋盤青柄；標準回溯處理；
使用回溯的具體做法是：依次在每一行放置一個皇后预侯，每次新放置的皇后都不能和已經(jīng)放置的皇后之間有攻擊致开，即新放置的皇后不能和任何一個已經(jīng)放置的皇后在同一列以及同一條斜線上。當 NNN 個皇后都放置完畢萎馅，則找到一個可能的解双戳，將可能的解的數(shù)量加 111。
image
解題代碼
var totalNQueens = function (n) {
let count = 0; //皇后可放置的總數(shù)
let isValid = (row, col, board, n) => {
//所在行不用判斷糜芳，每次都會下移一行
//判斷同一列的數(shù)據(jù)是否包含
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) => {
//走到最后一行飒货，統(tǒng)計次數(shù)
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] = '.'; //回溯，撤銷處理結(jié)果
}
}
}
backTracing(0, board)
let board = [...Array(n)].map(v => v = ([...Array(n)]).fill('.')) //棋盤
return count
};
2.4 - 78. 子集
給你一個整數(shù)數(shù)組 nums 峭竣，數(shù)組中的元素 互不相同 塘辅。返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復的子集皆撩。你可以按 任意順序 返回解集扣墩。
示例 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 中的所有元素 互不相同
解題思路
- 枚舉出所有可選的數(shù)；加入選項；
- 撤銷加入的選項呻惕，將選項加入結(jié)果
解題代碼
const subsets = (nums) => {
const res = [];
const backTracing = (index, list) => {
res.push(list.slice()); // 調(diào)用子遞歸前荆责，加入解集
for (let i = index; i < nums.length; i++) { // 枚舉出所有可選的數(shù)
list.push(nums[i]); // 選這個數(shù)
backTracing(i + 1, list); // 基于選這個數(shù)，繼續(xù)遞歸
list.pop(); // 撤銷選這個數(shù)
}
};
backTracing(0, []);
return res;
};
2.5 - 77. 組合
給定兩個整數(shù) n 和 k亚脆，返回范圍 [1, n] 中所有可能的 k 個數(shù)的組合做院。
你可以按 任何順序 返回答案。
示例 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
解題思路
- 枚舉出所有可選的數(shù)型酥；加入選項山憨；
- 撤銷加入的選項查乒，將選項加入結(jié)果
- 剪枝條件:選項的長度滿足條件弥喉；
image
解題代碼
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function (n, k) {
let result = [];
let backTracing = (start, path) => {
// 如果已經(jīng)選滿了的話，加入結(jié)果集中
if (path.length == k) {
result.push(path.slice());
return;
}
// 從開始的數(shù)字到末尾的數(shù)字
for (let i = start; i <= n; i++) {
// 加入選擇列表中
path.push(i);
// 繼續(xù)深度搜索
backTracing(i + 1, path);
// 撤銷選擇
path.pop(i);
}
};
backTracing(1, []);
return result;
};
2.6 - 081. 允許重復選擇元素的組合
給定一個無重復元素的正整數(shù)數(shù)組 candidates 和一個正整數(shù) target 玛迄，找出 candidates 中所有可以使數(shù)字和為目標數(shù) target 的唯一組合由境。
candidates 中的數(shù)字可以無限制重復被選取。如果至少一個所選數(shù)字數(shù)量不同蓖议，則兩種組合是唯一的虏杰。
對于給定的輸入，保證和為 target 的唯一組合數(shù)少于 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
解題思路
- 將當前元素加入到選項里面，并將計算結(jié)果修然，傳到選項笛钝，繼續(xù)遞歸；
- 當選項和大于目標值時愕宋，結(jié)束這個選項玻靡，直到找到符合的選項，并將選項加入結(jié)果中贝；
image
解題代碼
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);//選擇這個選項囤捻，繼續(xù)遞歸
visited.pop(); //插銷這個選擇
}
}
};
2.7 - 216. 組合總和 III
找出所有相加之和為 n 的 k 個數(shù)的組合。組合中只允許含有 1 - 9 的正整數(shù)邻寿，并且每種組合中不存在重復的數(shù)字蝎土。
說明：
所有數(shù)字都是正整數(shù)。
解集不能包含重復的組合绣否。
示例 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. 電話號碼的字母組合
給定一個僅包含數(shù)字 2-9 的字符串誊涯，返回所有它能表示的字母組合。答案可以按 任意順序 返回枝秤。
給出數(shù)字到字母的映射如下（與電話按鍵相同）醋拧。注意 1 不對應任何字母。
image
示例 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'] 的一個數(shù)字。
解題思路
- 找到當前按鈕對應的字母字符串
- 拼接按鈕對應的字符串組合
- 選項滿足長度丹壕，加入結(jié)果
image
解題代碼
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) { //選項滿足長度庆械，加入結(jié)果
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階琉用。實現(xiàn)一種方法堕绩，計算小孩有多少種上樓梯的方式。結(jié)果可能很大邑时，你需要對結(jié)果模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
};
動態(tài)規(guī)劃解法
/**
* @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
給定一個數(shù)組 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合晶丘。
candidates 中的每個數(shù)字在每個組合中只能使用一次黍氮。
注意：解集不能包含重復的組合。
示例 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
給定一個可包含重復數(shù)字的序列 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
};
三、總結(jié)
主要運用了回溯算法滚秩；而解決一個回溯問題专执，實際上就是一個決策樹的遍歷過程。
3.1 模板
let backtracking=(路徑郁油，選擇列表) =>{
if (滿足結(jié)束條件)) {
存放路徑;
return;
}
for (選擇：路徑本股，選擇列表) {
做出選擇；
backtracking(路徑已艰，選擇列表); // 遞歸
回溯痊末，撤銷處理結(jié)果
}
}
即:
- 1.路徑：也就是已經(jīng)做出的選擇。
- 2.選擇列表：也就是你當前可以做的選擇哩掺。
- 3.結(jié)束條件：也就是到達決策樹底層凿叠，無法再做選擇的條件。
3.2 剪枝函數(shù)
- 1.用約束條件剪除得不到的可行解的子樹
- 2.用目標函數(shù)剪取得不到的最優(yōu)解的子樹
3.3 回溯法的一般步驟：
- 1.設置初始化的方案（給變量賦初始值嚼吞，讀入已知數(shù)據(jù)等）
- 2.變換方式去試探盒件，若全部試完側(cè)轉(zhuǎn)（7）
- 3.判斷此法是否成功（通過約束函數(shù)），不成功則轉(zhuǎn)（2）
- 4.試探成功則前進一步再試探
- 5.正確方案還是未找到則轉(zhuǎn)（2）
- 6.以找到一種方案則記錄并打印
- 7.退回一步（回溯）舱禽，若未退到頭則轉(zhuǎn)（2）
- 8.已退到頭則結(jié)束或打印無解
繼續(xù)加油３吹蟆！誊稚！
四翔始、參考文獻
LeetCode 刷題筆記——遞歸與回溯的理解LeetCode 刷題筆記——遞歸與回溯的理解
圖解回溯算法圖解回溯算法
回溯算法總結(jié)回溯算法總結(jié)
