凯里市经济开发区建设局网站地方网站建设

DFS算法系列-回溯

1. 算法介绍

回溯算法是一种经典的递归算法，通常被用来解决排列问题、组合问题和搜索问题

基本思想

从一个初始状态开始，按一定的规则向前搜索，当搜索遇到瓶颈无法再前进时，回到当前状态的上一个状态，按照新的要求/条件继续向前搜索，直至所有可用条件都遍历完成。

简单的说就是：不撞南墙不回头

对于回溯算法，其核心就在于不断的"试错"，若选择正确则继续往下搜索，否则就"回头"选择另一个选项继续往下搜索。

下面提供一个回溯算法的模板（模板只是对算法理解的总结概况，相较于没有思考的套模板，理解其中的算法思想更加重要–>通过做题积累）

List<List<Integer>> ret;
List<Integer> path; void dfs(int[] nums, ...) {// 满⾜结束条件if (/* 满⾜结束条件 */) {// 将路径添加到结果集中ret.add(new ArrayList<>(path));return;}// 遍历所有选择for (int i = 0;i < nums.size();i++) {// 做出选择path.add(nums[i]);  // 做出当前选择后继续搜索dfs(path, nums);// 恢复现场path.remove(path.size() - 1);}
}

其中path用来记录每次选择后改变的路径，nums[i]表示当前做出的选择，并且在当前选择满足递归结束条件后，将当前路径添加到结果集中，结束当前层递归并恢复现场，即恢复刚刚完成修改的路径到上一个状态，才能继续处理当前层的另一个选择，如下图所示：

了解完回溯算法，我们来做一些相关的算法题加深印象！

2. 算法应用

对于回溯(以及DFS相关的题)，建议的解题步骤：

1. 先画决策树；
2. 根据决策树编写函数体，可设置全局变量、添加剪枝提高效率；
3. 找到递归出口

2.1 全排列

题目链接：[全排列]

决策树：

代码示例

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums);return ret;}void dfs(int[] nums) {if (path.size() == nums.length) {ret.add(new ArrayList(path));return;}for (int i = 0;i < nums.length;i++) { // 这里让i=0，使下一层选项依旧为所有情况(1,2,3,4)if (!check[i]) { // check数组用来记录当前数字是否被使用check[i] = true;   path.add(nums[i]); // 将数字添加到路径中dfs(nums);check[i] = false;path.remove(path.size() - 1);}}}
}

2.2 组合

题目链接：[组合]

决策树:

代码示例

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;int len;int pre;public List<List<Integer>> combine(int n, int k) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[n + 1];len = k;int[] nums = new int[n + 1];for (int i = 1;i <= n;i++) {nums[i] = i;}dfs(nums, 1);return ret;}public void dfs(int[] nums, int pos) {if (path.size() == len) { // 当路径长度和要求的组合数相等时返回ret.add(new ArrayList<>(path));return;}for (int i = pos;i <= nums.length - 1;i++) { // 这里让i=pos，使下一层选项不会出现当前数字,并且下层选项从pos+1开始if (!check[i]) {	path.add(nums[i]);  check[i] = true;dfs(nums, i + 1);path.remove(path.size() - 1);check[i] = false;}}}
}

注：这里让i=pos，使下一层选项不会出现当前数字,并且下层选项从pos+1开始；若为i = 0，则使下一层选项依旧为所有情况(1,2,3)：

2.3 子集

题目链接：[子集]

决策树：

代码示例

class Solution {static List<List<Integer>> ret;static List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int cur) {ret.add(new ArrayList<>(path)); // 此处不设出口目的是将每个节点路径都添加到ret中for (int i = cur;i < nums.length;i++) { // 这里让i=cur，使下一层选项不会出现当前数字，并且下层选项从cur+1开始path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1); }}
}

3. 总结

总的来说，回溯就是不断的"试错"并回头进行新的选择，和回溯相关的题就要把决策树画出来，通过它来找到我们的递归出口并编写函数体(注意for循环中起始标的使用)，注意记得恢复现场哦!