个人网站可以做商业吗,中小企业网站建设多少钱,搜索百度一下,深圳营销型网站建设价格DFS算法系列-回溯 文章目录 DFS算法系列-回溯1. 算法介绍2. 算法应用2.1 全排列2.2 组合2.3 子集 3. 总结 1. 算法介绍
回溯算法是一种经典的递归算法#xff0c;通常被用来解决排列问题、组合问题和搜索问题
基本思想 从一个初始状态开始#xff0c;按一定的规则向前搜索通常被用来解决排列问题、组合问题和搜索问题
基本思想 从一个初始状态开始按一定的规则向前搜索当搜索遇到瓶颈无法再前进时回到当前状态的上一个状态按照新的要求/条件继续向前搜索直至所有可用条件都遍历完成。 简单的说就是不撞南墙不回头
对于回溯算法其核心就在于不断的试错若选择正确则继续往下搜索否则就回头选择另一个选项继续往下搜索。
下面提供一个回溯算法的模板模板只是对算法理解的总结概况相较于没有思考的套模板理解其中的算法思想更加重要–通过做题积累
ListListInteger ret;
ListInteger 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相关的题)建议的解题步骤
先画决策树根据决策树编写函数体可设置全局变量、添加剪枝提高效率找到递归出口
2.1 全排列
题目链接[全排列]
决策树 代码示例
class Solution {ListListInteger ret;ListInteger path;boolean[] check;public ListListInteger 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) { // 这里让i0使下一层选项依旧为所有情况(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 {ListListInteger ret;ListInteger path;boolean[] check;int len;int pre;public ListListInteger 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) { // 这里让ipos使下一层选项不会出现当前数字,并且下层选项从pos1开始if (!check[i]) { path.add(nums[i]); check[i] true;dfs(nums, i 1);path.remove(path.size() - 1);check[i] false;}}}
}注这里让ipos使下一层选项不会出现当前数字,并且下层选项从pos1开始若为i 0则使下一层选项依旧为所有情况(1,2,3) 2.3 子集
题目链接[子集]
决策树 代码示例
class Solution {static ListListInteger ret;static ListInteger path;public ListListInteger 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) { // 这里让icur使下一层选项不会出现当前数字并且下层选项从cur1开始path.add(nums[i]);dfs(nums, i 1);path.remove(path.size() - 1); }}
}3. 总结
总的来说回溯就是不断的试错并回头进行新的选择和回溯相关的题就要把决策树画出来通过它来找到我们的递归出口并编写函数体(注意for循环中起始标的使用)注意记得恢复现场哦!
