1 简介
回溯算法是一种基于试错思想的搜索算法，也是一种重要的编程技巧，常用于解决组合、排列、切割等问题。它通过不断尝试解决问题的每一步，一旦发现当前步骤不能得到有效的正确解，就会返回上一步或多步，并尝试其他可能的分步解决方案。这种策略使得回溯算法能够有效地找到问题的所有可行解或最优解。
2 理论基础
- 试错思想: 回溯算法的核心是试错思想，它尝试每一个可能的解决方案，并在发现当前方案不可行时撤销前一步或几步的操作。
- 深度优先搜索（dfs）: 回溯算法与深度优先搜索紧密相关，通过尽可能深地搜索树的分支来寻找问题的解。
- 递归实现: 回溯算法通常采用递归方式实现，因为递归调用可以很自然地映射到算法的回溯（即返回上一层）操作上。
3 应用场景
1. 组合问题: 从给定个数的元素中，按照一定的规则选择元素形成组合。
应用实例：旅行商问题（TSP）：这类问题要求找出最短可能路径，使得每个城市只访问一次并返回起点。
2. 排列问题: 找出所有可能的排列方式。
应用实例: 全排列问题。经典的全排列问题要求对一组数字进行所有可能的排列，例如对于数字集合{1, 2, 3}，求出所有六个可能的排列。
3. 数独问题:填写9×9的方格，使得每行、每列和每个宫内的数字均不重复。
应用实例: 数独求解器。数独游戏要求在9×9的网格中填入数字，每行、每列及9个3×3的子网格中的数字（1-9）均不重复。
4. 决策问题:在多个可选方案中寻找最优解，通常涉及多个约束条件。
应用实例: 作业调度。例如，在生产线上，需要安排不同作业执行的顺序，以优化生产效率和资源利用率。
5. 棋盘问题: 在N×N的棋盘上放置N个“皇后”，使得它们互不攻击。
应用实例: 八皇后问题。这是一个经典的回溯算法问题，要求在8×8的棋盘上放置8个皇后，使得它们不会互相攻击。
6. 切割问题:将字符串或数组按照规定的方式进行分割。
应用实例: 字符串分割。例如，将一个字符串按一定规则分割成多个有效的子串。
7. 递增子序列问题:找出数组或列表中的递增子序列。
应用实例:最长递增子序列。在一个数字序列中找到最长的递增子序列。
8. 搜索问题:在图或网络中搜索从起点到终点的有效路径。
应用实例:图的深度优先搜索。例如，在地图导航系统中，搜索从一个地点到另一个地点的所有可能路线。
4 算法流程
- 选择：从当前状态的所有可选方案中选择一个进行下一步尝试。
- 约束：检查当前状态是否满足给定的约束条件。
- 目标：判断当前状态是否是目标状态，即是否找到了一个符合要求的解。
- 回溯：当发现当前状态不可行或已经找到一个解时，返回上一步的状态，继续尝试其他可能的选项。
公式就参考carl哥的回溯三部曲了
- 回溯函数模板返回值以及参数
- 回溯函数终止条件
- 回溯搜索的遍历过程
框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}5 实例
5.1 简单题
257. 二叉树的所有路径
给你一个二叉树的根节点
root，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]示例 2：
输入：root = [1] 输出：["1"]提示：
- 树中节点的数目在范围
[1, 100]内-100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
bfs(root, "", res);
return res;
}
public void bfs(TreeNode root, String path, List<String> paths){
if(root == null){
// 终止节点
return;
}
StringBuilder sb = new StringBuilder(path);
sb.append(Integer.toString(root.val));
if(root.left == null && root.right == null){
// 遍历到叶子结点结束
paths.add(sb.toString());
}else{
// 由于是二叉树，先序遍历即可
sb.append("->");
bfs(root.left, sb.toString(), paths);
bfs(root.right, sb.toString(), paths);
}
}
}5.2 经典中等题
39. 组合总和
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target的不同组合数少于150个。示例 1：
输入：candidates =[2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3：
输入: candidates =[2], target = 1 输出: []提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
class Solution {
List<Integer> path = new ArrayList<Integer>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
dfs(candidates, target, 0, 0);
return res;
}
public void dfs(int[] nums, int target, int index, int sum) {
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
// 非结果直接忽略
if (sum > target){
return;
}
for (int i = index; i < nums.length; i++) {
// 加入当前值
path.add(nums[i]);
sum += nums[i];
dfs(nums, target, i, sum);
// 回溯
path.remove(path.size() - 1);
sum -= nums[i];
}
}
}5.3 困难题
51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：[["Q"]]提示：
1 <= n <= 9
对于三皇后图解：
三皇后本无解，一步一步递归验证，终可得出结论。如下图：
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (char[] c : chessboard) {
Arrays.fill(c, '.');
}
backTracking(n, 0, chessboard);
return res;
}
public void backTracking(int n, int row, char[][] chessboard) {
if (row == n) {
res.add(Array2List(chessboard));
return;
}
for (int col = 0; col < n; ++col) {
if (isValid(row, col, n, chessboard)) {
chessboard[row][col] = 'Q';
backTracking(n, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
}
// 数组转换
public List Array2List(char[][] chessboard) {
List<String> list = new ArrayList<>();
for (char[] c : chessboard) {
list.add(String.copyValueOf(c));
}
return list;
}
// 判断当前节点是否符合规范
public boolean isValid(int row, int col, int n, char[][] chessboard) {
// 检查列
for (int i = 0; i < row; ++i) {
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查45度对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查135度对角线
for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}6 回溯算法的优缺点
- 优点：
- 能够找到所有可能的解决方案。
- 易于理解和实现。
- 适合解决复杂问题。
- 缺点：
- 时间复杂度高，尤其是问题规模较大时。
- 可能会产生大量的重复计算。
- 需要较多的存储空间来保存中间状态。
7 总结
总的来说，回溯算法是一种强大的问题解决工具，特别适合处理那些可以通过逐步构建解决方案来解决的问题。然而，由于其高时间复杂度和空间需求，在实际应用中可能需要进行适当的优化。通过剪枝、约束加强、启发式搜索等策略，可以有效提高回溯算法的效率，使其更好地应用于实际问题中。
标签：return,target,--,chessboard,int,算法,回溯,root From： https://blog.csdn.net/qq_67342067/article/details/141122531