什么是回溯算法
回溯算法是一种通用的算法。回溯法采纳试错的思维，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能失去无效的正确的解答的时候，它将勾销上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简略的递归办法来实现，在重复反复上述的步骤后可能呈现两种状况：
- 找到一个可能存在的正确的答案
- 在尝试了所有可能的分步办法后宣告该问题没有答案
在最坏的状况下，回溯法会导致一次复杂度为指数工夫的计算。回溯算法的实质就是暴力的递归搜寻，当然在理论的操作中。能够通过适当的剪枝以缩小工夫复杂度。
leetcode回溯算法相干题目解答
以下题目均来自leetcode
???? 子集
思路
本题须要留神的是，因为不能蕴含反复的子集([1,2,3],[3,1,2]是属于反复的)，所以"3"这个节点下，不须要增加"1"和"2"节点进行递归操作，回产生反复的汇合。
解答
/** * @param {number[]} nums * @return {number[][]} */var subsets = function(nums) { const result = [] result.push([]) const fn = (head, tail) => { for (let i = 0; i < tail.length; i++) { result.push([...head, tail[i]]) if (tail.slice(i + 1)) { fn([...head, tail[i]], tail.slice(i + 1)) } } } for (let i = 0; i < nums.length; i++) { result.push([nums[i]]) if (nums.slice(i + 1).length) { fn([nums[i]], nums.slice(i + 1)) } } return result;};???? 子集 II
思路
首先将数组进行排序。排序的目标是将相等的元素，挪动到相邻的地位。咱们在遍历数组的时候，判读以后的值和前一个的值是否相等，如果相等则跳过
解答
???? 同层减枝去重
/** * @param {number[]} nums * @return {number[][]} */var subsetsWithDup = function(nums) { const result = [] result.push([]) nums.sort((a, b) => a - b) const fn = (head, tail) => { for (let i = 0; i < tail.length; i++) { if (tail[i] === tail[i - 1]) { continue } else { result.push([...head, tail[i]]) if (tail.slice(i + 1)) { fn([...head, tail[i]], tail.slice(i + 1)) } } } } for (let i = 0; i < nums.length; i++) { if (nums[i] === nums[i - 1]) { continue } else { result.push([nums[i]]) if (nums.slice(i + 1).length) { fn([nums[i]], nums.slice(i + 1)) } } } return result;};???? 另外的思路，应用hash去重
/** * @param {number[]} nums * @return {number[][]} */var subsetsWithDup = function(nums) { const result = [] const hash = {} result.push([]) nums.sort((a, b) => a - b) const fn = (head, tail) => { for (let i = 0; i < tail.length; i++) { let key = [...head, tail[i]].join(',') if (!hash[key]) { result.push([...head, tail[i]]) hash[key] = true; } if (tail.slice(i + 1)) { fn([...head, tail[i]], tail.slice(i + 1)) } } } for (let i = 0; i < nums.length; i++) { let key = [nums[i]].join(',') if (!hash[key]) { result.push([nums[i]]) hash[key] = true; } if (nums.slice(i + 1).length) { fn([nums[i]], nums.slice(i + 1)) } } return result;};???? 组合
思路
n，是咱们的取值范畴。k是咱们的递归次数。当递归的次数等于2时，完结递归。将满足条件的增加到result中，并返回。
解答
/** * @param {number} n * @param {number} k * @return {number[][]} */var combine = function(n, k) { const arr = [] const result = [] // 初始化 for (let i = 1; i <= n; i++) { arr.push(i) } if (arr.length === k) { // 如果k等于长度，间接返回汇合 return [arr]; } const fn = (head, tail, k) => { if (k <= 0) { result.push(head) } else { for (let i = 0; i < tail.length; i++) { fn([...head, tail[i]], tail.slice(i + 1), k - 1) } } } for (let i = 0; i < arr.length; i++) { if (k > 0) { fn([arr[i]], arr.slice(i + 1), k - 1); } } return result;};???? 组合总和
思路
尽管汇合中的数字是能够反复利用的。为了进行优化，咱们还是须要做适当的减枝，防止做过多的递归。比方"2"节点的子节点是"2,3,6,7"。"3"节点的子节点是"3,6,7", 为什么没有"2"呢？因为如果有"2",会和之前的"2->3"反复，所以能够少递归这一条分支。
解答
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */var combinationSum = function(candidates, target) { const result = [] candidates.sort((a, b) => a - b) const fn = (arr, sum, index) => { if (sum > target) { return } if (sum === target) { result.push(arr) } else { // i = index, 防止反复的递归，同时防止反复 for (let i = index; i < candidates.length; i++) { fn([...arr, candidates[i]], sum + candidates[i], i) } } } for (let i = 0; i < candidates.length; i++) { if (candidates[i] === target) { result.push([candidates[i]]) } else { fn([candidates[i]], candidates[i], i) } } return result;};???? 组合总和 II
思路
思路和组合总和统一。只是多了一些判读条件。首先将数组排序，把大小相等的元素集中在一起。在递归的视频，判读以后和前一个元素是否相等，如果相等则跳过。防止反复的组合。
留神这里是不能重复使用同一个数字，不是不能蕴含反复的数字。，所以呈现反复的数字是容许的，增加上述判读条件的目标是为了呈现反复的组合。见下图：
解答
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */var combinationSum2 = function(candidates, target) { const result = [] candidates = candidates.sort((a, b) => a - b) const fn = (sum, arr, candidates) => { if (sum > target) { return } if (sum === target) { result.push(arr) } else { for (let i = 0; i < candidates.length; i++) { if (candidates[i] !== candidates[i - 1]) { let temp = candidates.slice(i + 1) fn(sum + candidates[i], [...arr, candidates[i]], temp) } } } } for (let i = 0; i < candidates.length; i++) { if (candidates[i] === target && candidates[i] !== candidates[i - 1]) { result.push([candidates[i]]) } else if (candidates[i] !== candidates[i - 1]) { let temp = candidates.slice(i + 1) fn(candidates[i],[candidates[i]],temp) } } return result;};???? 组合总和 III
思路
和“组合”题目相似，k就是咱们的递归次数。n是咱们的target，当递归层数达到k时，完结递归。同时将满足条件的组合，增加到后果中
解答
/** * @param {number} k * @param {number} n * @return {number[][]} */var combinationSum3 = function(k, n) { const result = []; const candidates = []; const target = n; // 初始化 for (let i = 1; i <= 9; i++) { candidates.push(i) } const fn = (sum, arr, candidates, k) => { if (k >= 0) { if (k === 0) { if (sum === target) { result.push(arr) } } else { for (let i = 0; i < candidates.length; i++) { const temp = candidates.slice(i + 1) fn( sum + candidates[i], [...arr, candidates[i]], [...temp], k - 1 ); } } } } for (let i = 0; i < candidates.length; i++) { if (k === 1 && candidates[i] === target) { result.push([candidates[i]]) } else { const temp = candidates.slice(i + 1) fn( candidates[i], [candidates[i]], [...temp], k - 1 ) } } return result;};???? 电话号码的字母组合
思路
// 电话号码数字对应的字母{ 2: ['a', 'b', 'c'], 3: ['d', 'e', 'f'], 4: ['g', 'h', 'i'], 5: ['j', 'k', 'l'], 6: ['m', 'n', 'o'], 7: ['p', 'q', 'r', 's'], 8: ['t', 'u', 'v'], 9: ['w', 'x', 'y', 'z']}解答
/** * @param {string} digits * @return {string[]} */var letterCombinations = function(digits) { const map = { 2: ['a', 'b', 'c'], 3: ['d', 'e', 'f'], 4: ['g', 'h', 'i'], 5: ['j', 'k', 'l'], 6: ['m', 'n', 'o'], 7: ['p', 'q', 'r', 's'], 8: ['t', 'u', 'v'], 9: ['w', 'x', 'y', 'z'] } const arr = digits.split('') const result = [] const fn = (head, arr) => { if (arr.length) { const key = arr.splice(0, 1)[0] const collection = map[key] for (let i = 0; i < collection.length; i++) { fn(`${head}${collection[i]}`, [...arr]) } } else { if (head) { result.push(head) } } } fn('', [...arr]); return result;};全排列
思路
留神曾经增加到后果中的数字，不参加下次递归。
解答
/** * @param {number[]} nums * @return {number[][]} */var permute = function(nums) { const result = [] const fn = (head, tail) => { for (let i = 0; i < tail.length; i++) { let temp = [...tail] temp.splice(i, 1) if (temp.length) { fn([...head, tail[i]], temp); } else { result.push([...head, tail[i]]) } } } for (let i = 0; i < nums.length; i++) { let temp = [...nums] temp.splice(i, 1) if (temp.length) { fn([nums[i]], temp); } else { result.push([nums[i]]) } } return result;};全排列 II
思路
思路和之前的题目都是相似的，首先对数组进行排序，目标是将相等的数字集中到一起。如果在同一层的递归中呈现同样的数字，跳过。避免出现反复的排列。
解答
???? 应用hash去重
/** * @param {number[]} nums * @return {number[][]} */var permuteUnique = function(nums) { const result = [] const hash = {} nums.sort((a, b) => a - b) const fn = (head, tail) => { for (let i = 0; i < tail.length; i++) { let temp = [...tail] temp.splice(i, 1) if (temp.length) { fn([...head, tail[i]], temp); } else { let key = [...head, tail[i]].join(','); if (!hash[key]) { result.push([...head, tail[i]]) hash[key] = true } } } } for (let i = 0; i < nums.length; i++) { let temp = [...nums] temp.splice(i, 1) if (temp.length) { fn([nums[i]], temp); } else { result.push([nums[i]]) } } return result;};???? 同层剪枝
/** * @param {number[]} nums * @return {number[][]} */var permuteUnique = function(nums) { const result = [] nums.sort((a, b) => a - b) const fn = (head, tail) => { for (let i = 0; i < tail.length; i++) { let temp = [...tail] temp.splice(i, 1) if (tail[i] !== tail[i - 1]) { if (temp.length) { fn([...head, tail[i]], temp); } else { result.push([...head, tail[i]]) } } } } for (let i = 0; i < nums.length; i++) { let temp = [...nums] temp.splice(i, 1) if (nums[i] !== nums[i - 1]) { if (temp.length) { fn([nums[i]], temp); } else { result.push([nums[i]]) } } } return result;};???? 还原IP地址
思路
终于看到一个不那么雷同的题目了。之前的全排列，组合，组合总合。解答过程都是大同小异的。
首先确定下本题下,IP地址是否非法的判断条件，首先须要有4组数字组合，每一组数字大小范畴在0～255（蕴含255），其中不能蕴含前置的0。也就是说"02","022"是不合规的。
题目提供了一段数字，根据上述的规定，咱们须要在这段数字中增加3个点对这个数字进行宰割（也就是说须要递归3层）。咱们把递归的过程用图示意进去（因为分叉太多，所以图片并不残缺，还请见谅）
橘红色的代表，IP地址不合规的，无奈持续迭代上来。
解答
/** * @param {string} s * @return {string[]} */var restoreIpAddresses = function(s) { const result = []; const isLegal = (n) => { if (n.length <= 0) { return false } if (n.length > 1 && n[0] === '0') { return false } if (Number(n) > 255 || Number(n) < 0) { return false } return true } const fn = (head, tail, n) => { if (n <= 0) { if (isLegal(tail)) { result.push(`${head}.${tail}`) } } else { for (let i = 0; i < 3; i++) { const h = tail.slice(0, i + 1); if (isLegal(h)) { let newHead = '' if (head.length) { newHead = `${head}.${h}`; } else { newHead = `${h}`; } const t = tail.slice(i + 1); fn(newHead, t, n - 1); } } } }; fn('', s, 3); return result;};括号生成
思路
在进行回溯之前，首先须要确定下，递归的终止条件。
在一段括号组成的字符串中，增加'('是无需判断条件的，然而增加')'是须要额定的判断条件。只有在这段字符串'('的数量大于')'的状况下，才容许增加')'
比方: '(())'，在这个时候增加')'字符串，括号将永远无奈闭合。再比方，'()((', 就能够增加')'字符串。
咱们应用下图，来形容回溯的过程
解答
/** * @param {number} n * @return {string[]} */var generateParenthesis = function(n) { const result = [] const left = [] const rigth = [] const fn = (head, leftNum, rightNum) => { if (leftNum === n && rightNum === n) { result.push(head) } else { if (leftNum >= rightNum) { if (leftNum < n) { fn(`${head}(`, leftNum + 1, rightNum) } if (rightNum < n && rightNum + 1 <= leftNum) { fn(`${head})`, leftNum, rightNum + 1) } } } } fn('', 0, 0); return result;};???? N皇后
思路
终于讲到了N皇后问题。先说下解决这题的思路，仍然是应用递归的办法。咱们首先假设第一个Queen在[0, 0]的地位，而后确定第一个Queen的攻打范畴（既之后的Queen不能放的地位）。接着开始遍历棋盘的第二行，找到能够放的地位，并记录第二个Queen的攻打地位，之后的Queen要同时防止第一个Queen和第二个Queen的攻打地位。而后开始查找第三行。
如果找不到，咱们须要向上回溯到第一行。并同时把第二行Queen的攻打地位，复原到能够搁置的状态。而后将第一个Queen挪动到[0, 2]的地位。而后接着遍历棋盘的第二行。
对于Queen的攻打范畴，在国际象棋中Queen能够攻打直线，横线，左斜线，右斜线的敌人。比方下图，红色的局部就是Queen的攻打范畴。攻打范畴内，是不能搁置第二个Queen的。
直线的攻打范畴容易确定，斜线的攻打范畴呢？应用 4 * 4 的棋盘阐明，左斜线能够分为 3 2 1 0 -1 -2 -3 , 7条斜线。
右斜线能够分为 1，2，3，4，5，6 , 7条斜线。
咱们应用hash记录攻打范畴
const letDiagonalAttackRange = { 3: true, 2: true, 1: true, 0: true, -1: true, -2: true, -3: true}const rightDiagonalAttackRange = { 0: true, 1: true, 2: true, 3: true, 4: true, 5: true, 6: true,}比方当Queen在[1， 1]的地位时，咱们将letDiagonalAttackRange[0]和rightDiagonalAttackRange[2]设置为false，之后的Queen静止到坐标x+y等于2，或者x-y等于0，的地位时。就能搁置，只能持续向后查找。
解答
/** * @param {number} n * @return {string[][]} */var solveNQueens = function(n) { const result = [] const rowAttackRange = {} const colAttackRange = {} const letDiagonalAttackRange = {} const rightDiagonalAttackRange = {} const initializeAttackRange = () => { // 初始化直线攻打范畴 for (let i = 0; i < n; i++) { rowAttackRange[i] = true colAttackRange[i] = true } // 初始化斜线攻打范畴 for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { letDiagonalAttackRange[i + j] = true rightDiagonalAttackRange[i - j] = true } } } initializeAttackRange() // 判读是否容许搁置 const isPlace = (x, y) => { if (rowAttackRange[y] && colAttackRange[x] && letDiagonalAttackRange[y + x] && rightDiagonalAttackRange[y - x]) { return true } return false } const fn = (row, collection) => { if (row === n) { result.push([...collection]) return } else { for (let j = 0; j < n; j++) { if (isPlace(j, row)) { rowAttackRange[row] = false colAttackRange[j] = false letDiagonalAttackRange[row + j] = false rightDiagonalAttackRange[row - j] = false collection.push({ x: j, y: row, }) fn(row + 1, collection) // 如果从这个格子往下没有取得解，须要还原 rowAttackRange[row] = true colAttackRange[j] = true letDiagonalAttackRange[row + j] = true rightDiagonalAttackRange[row - j] = true collection.pop() } } } } for (let j = 0; j < n; j++) { let temp = [ { x: j, y: 0 } ]; rowAttackRange[0] = false colAttackRange[j] = false letDiagonalAttackRange[0 + j] = false rightDiagonalAttackRange[0 - j] = false fn( 1, temp ) rowAttackRange[0] = true colAttackRange[j] = true letDiagonalAttackRange[0 + j] = true rightDiagonalAttackRange[0 - j] = true } // 对result做解决 for (let i = 0; i < result.length; i++) { let temp = new Array(n).fill(new Array(n).fill('.')) for (let j = 0; j < n; j++) { const { x, y } = result[i][j] const arr = [...temp[y]] arr[x] = 'Q' temp[y] = arr.join('') } result[i] = temp } return result};参考
- 回溯法Wiki
- leetcode