一、回溯算法

1.1 什么是回溯？

回溯算法实际上一个相似枚举的搜寻尝试过程，次要是在搜寻尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的门路。——摘自《百度百科》

1.1 个别步骤：

1. 针对所给问题，定义问题的解空间，它至多蕴含问题的一个（最优）解。
2. 确定易于搜寻的解空间结构, 使得能用回溯法不便地搜寻整个解空间。
3. 以深度优先的形式搜寻解空间，并且在搜寻过程中用剪枝函数防止有效搜寻。

1.2 如何了解回溯算法？

1. 为问题建设解空间结构
2. 在解空间结构上进行 DFS 搜寻
3. 设立回溯进口和剪枝点，缩小有效搜寻，出口处保留无效解.

1.3 解决那些问题？

1. 组合问题：N 个数⾥⾯按⼀定规定找出 k 个数的汇合
2. 切割问题：⼀个字符串按⼀定规定有⼏种切割⽅式
3. ⼦集问题：⼀个 N 个数的汇合⾥有多少符合条件的⼦集
4. 排列问题：N 个数按⼀定规定全排列，有⼏种排列⽅式
5. 棋盘问题：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

思路剖析

1. 判断左右括号所剩的数量，最初始都是 n; 当左括号（(）有残余，持续做抉择；
2. 判断当右括号比左括号剩的多，能力选右括号；持续递归做抉择
3. 进口: 构建的字符串是 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 中的所有整数 互不雷同

解题思路

1. 回溯终止条件：该条门路长度与达到 nums 长度；
2. 退出以后值到门路，如果后果外面曾经蕴含这个门路，则不退出后果外面，否则持续抉择这个选项；

解题代码

/**
 * @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

解题思路

1. 定义判断以后地位的检验函数，约束条件蕴含，不能同行，不能同列，不能同对角线（45 度和 135 度）
2. 定义棋盘；规范回溯解决；

应用回溯的具体做法是：顺次在每一行搁置一个皇后，每次新搁置的皇后都不能和曾经搁置的皇后之间有攻打，即新搁置的皇后不能和任何一个曾经搁置的皇后在同一列以及同一条斜线上。当 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 中的所有元素 互不雷同

解题思路

1. 枚举出所有可选的数；退出选项；
2. 撤销退出的选项，将选项退出后果

解题代码

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

解题思路

1. 枚举出所有可选的数；退出选项；
2. 撤销退出的选项，将选项退出后果
3. 剪枝条件: 选项的长度满足条件；

解题代码

/**
 * @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

解题思路

1. 将以后元素退出到选项外面，并将计算结果，传到选项，持续递归；
2. 当选项和大于目标值时，完结这个选项，直到找到合乎的选项，并将选项退出后果；

解题代码

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’] 的一个数字。

解题思路

1. 找到以后按钮对应的字母字符串
2. 拼接按钮对应的字符串组合
3. 选项满足长度，退出后果

解题代码

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. 1. 门路：也就是曾经做出的抉择。
2. 2. 抉择列表：也就是你以后能够做的抉择。
3. 3. 完结条件：也就是达到决策树底层，无奈再做抉择的条件。

3.2 剪枝函数

1. 1. 用约束条件剪除得不到的可行解的子树
2. 2. 用指标函数剪获得不到的最优解的子树

3.3 回溯法的个别步骤：

1. 1. 设置初始化的计划（给变量赋初始值，读入已知数据等）
2. 2. 变换形式去试探，若全副试完侧转（7）
3. 3. 判断此法是否胜利（通过束缚函数），不胜利则转（2）
4. 4. 试探胜利则前进一步再试探
5. 5. 正确计划还是未找到则转（2）
6. 6. 以找到一种计划则记录并打印
7. 7. 退回一步（回溯），若未退到头则转（2）
8. 8. 已退到头则完结或打印无解

持续加油！！！

# 四、参考文献

1. LeetCode 刷题笔记——递归与回溯的了解 LeetCode 刷题笔记——递归与回溯的了解

2. 图解回溯算法图解回溯算法
3. 回溯算法总结回溯算法总结