怎么样做购物网站,网站建设学习网公司有哪些,搭建网页游戏平台,应该如何做营销型网站目录
什么是回溯算法#xff1a; 子集问题#xff1a;
子集问题II(元素可重复但不可复选): 组合问题#xff1a;
组合问题II(组合总和):
组合问题III(组合总和II):
排列问题#xff1a;
排列问题II(元素可重复但不可复选):
排列问题III(元素无重复但可复选):
最后…目录
什么是回溯算法 子集问题
子集问题II(元素可重复但不可复选): 组合问题
组合问题II(组合总和):
组合问题III(组合总和II):
排列问题
排列问题II(元素可重复但不可复选):
排列问题III(元素无重复但可复选):
最后总结 什么是回溯算法
「回溯是递归的副产品只要有递归就会有回溯」所以回溯法也经常和二叉树遍历深度优先搜索混在一起因为这两种方式都使用了递归。 详细地说可以将回溯算法过程理解成一颗多叉树的遍历过程 回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树当算法搜索至解空间树的某一节点时先利用剪枝函数判断该节点是否可行即能得到问题的解。如果不可行则跳过对该节点为根的子树的搜索逐层向其祖先节点回溯否则进入该子树继续按深度优先策略搜索。 回溯问题的基本框架 void backtrack(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {//注意i0,istart的区别处理节点;backtrack(路径选择列表); // 递归 注意(i)和(i)的区别 回溯撤销处理结果}
} 多叉树的遍历
与二叉树的遍历类似但要遍历所有的子节点 public void traverse(TreeNode root){if(root null){return ;}//前序遍历的位置for(Node child : root.children){traverse(child);}//后序遍历的位置}如果将前后续遍历的位置放到for循环里面与上图的区别在于不遍历根节点通过后面例题加深理解
那么有了上面的一定了解后我们看下例题具体怎么使用框架 子集问题
问题描述
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 题目链接78. 子集 - 力扣LeetCode
这是一个典型的回溯问题首先我们将它模拟成一颗多叉树根节点为空 解决这个问题的关键在于如何遍历这颗多叉树并且子集不重复 在遍历的过程中我们要将每一个节点都收录到集合中最后返回这个集合。之后我们只需要让子集不重复就好了这里我们可以通过设定一个变量start来记录当前走过的位置使其不断1来进行迭代保证不重复具体实现如下
class Solution {//定义二维数组res用于存储结果ListListInteger res new LinkedList();//定义路径数组LinkedListInteger track new LinkedList(); public ListListInteger subsets(int[] nums) {backtrack(nums,0);return res;}void backtrack(int[] nums,int start){//添加路径数组到结果数组中res.add(new LinkedList(track));//for循环遍历数组nums这里相当于遍历这颗多叉树for(int i start;i nums.length;i){//做选择将选择添加到路径数组中track.add(nums[i]);//回溯继续向后遍历backtrack(nums,i 1);//撤销选择将选择从路径中删除track.removeLast();}}
}
子集问题II(元素可重复但不可复选):
题目链接90. 子集 II - 力扣LeetCode
输入输出样例 这里我们以例一为例为了区别两个 2 是不同元素后面我们写作 nums [1,2,2]。
按照之前的思路画出子集的树形结构显然两条值相同的相邻树枝会产生重复 这里我们需要进行剪枝同时为了方便剪枝这里我们需要将数组进行排序将形同的元素靠在一起如果一个节点有多条值相同的树枝相邻则只遍历第一条剩下的都剪掉不要去遍历 体现在代码上需要先进行排序让相同的元素靠在一起如果发现 nums[i] nums[i-1]则跳过
class Solution {ListListInteger res new LinkedList();LinkedListInteger track new LinkedList();public ListListInteger subsetsWithDup(int[] nums) {// 先排序让相同的元素靠在一起Arrays.sort(nums);backtrack(nums, 0);return res;}void backtrack(int[] nums, int start) {// 前序位置每个节点的值都是一个子集将他们收集res.add(new LinkedList(track));for (int i start; i nums.length; i) {// 剪枝逻辑值相同的相邻树枝只遍历第一条if (i start nums[i] nums[i - 1]) {continue;}//选择操作track.addLast(nums[i]);//回溯backtrack(nums, i 1);//撤销选择track.removeLast();}}
} 组合问题 题目描述
给定两个整数 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]]
题目链接77. 组合 - 力扣LeetCode
还是以 nums [1,2,3] 为例刚才让我们求所有子集就是把所有节点的值都收集起来现在我们只需要把第 2 层根节点视为第 0 层的节点收集起来就是大小为 2 的所有组合 class Solution {ListListInteger res new LinkedList();// 记录回溯算法的递归路径LinkedListInteger track new LinkedList();// 主函数public ListListInteger combine(int n, int k) {backtrack(1, n, k);return res;}void backtrack(int start, int n, int k) {// base caseif (k track.size()) {// 遍历到了第 k 层收集当前节点的值res.add(new LinkedList(track));return;}// 回溯算法标准框架for (int i start; i n; i) {// 选择track.addLast(i);// 通过 start 参数控制树枝的遍历避免产生重复的子集backtrack(i 1, n, k);// 撤销选择track.removeLast();}}
}
组合问题II(组合总和):
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。 题目链接39. 组合总和 - 力扣LeetCode
上述子集问题中我们通过变量start1来控制树的生成也就是剪枝但是这题可以无限制选用一个数字那么剪枝也就没有必要了这里我们保持start不变树会一直生成只需改变base case限制条件就行了同时定义一个trackSum来维护路径和
class Solution {ListListInteger res new LinkedList();// 记录回溯的路径LinkedListInteger track new LinkedList();// 记录 track 中的路径和int trackSum 0;public ListListInteger combinationSum(int[] candidates, int target) {if (candidates.length 0) {return res;}backtrack(candidates, 0, target);return res;}// 回溯算法主函数void backtrack(int[] nums, int start, int target) {// base case找到目标和记录结果if (trackSum target) {res.add(new LinkedList(track));return;}// base case超过目标和停止向下遍历if (trackSum target) {return;}// 回溯算法标准框架for (int i start; i nums.length; i) {// 选择 nums[i]trackSum nums[i];track.add(nums[i]);// 递归遍历下一层回溯树// 同一元素可重复使用注意参数backtrack(nums, i, target);// 撤销选择 nums[i]trackSum - nums[i];track.removeLast();}}
}
组合问题III(组合总和II):
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。 与子集II类似我们只需多一个剪枝操作即可
class Solution {ListListInteger res new LinkedList();// 记录回溯的路径LinkedListInteger track new LinkedList();// 记录 track 中的元素之和int trackSum 0;public ListListInteger combinationSum2(int[] candidates, int target) {if (candidates.length 0) {return res;}// 先排序让相同的元素靠在一起Arrays.sort(candidates);backtrack(candidates, 0, target);return res;}// 回溯算法主函数void backtrack(int[] nums, int start, int target) {// base case达到目标和找到符合条件的组合if (trackSum target) {res.add(new LinkedList(track));return;}// base case超过目标和直接结束if (trackSum target) {return;}// 回溯算法标准框架for (int i start; i nums.length; i) {// 剪枝逻辑值相同的树枝只遍历第一条if (i start nums[i] nums[i - 1]) {continue;}// 做选择track.add(nums[i]);trackSum nums[i];// 递归遍历下一层回溯树backtrack(nums, i 1, target);// 撤销选择track.removeLast();trackSum - nums[i];}}
}排列问题
题目描述给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 题目链接46. 全排列 - 力扣LeetCode
刚才讲的组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start1..] 中的元素通过固定元素的相对位置保证不出现重复的子集。但排列问题本身就是让你穷举元素的位置nums[i] 之后也可以出现 nums[i] 左边的元素所以之前的那一套玩不转了需要额外使用 used 数组来标记哪些元素还可以被选择这就相当于剪枝的作用。将全排列问题模拟成一颗多叉树 class Solution {ListListInteger res new LinkedList();// 记录回溯算法的递归路径LinkedListInteger track new LinkedList();// track 中的元素会被标记为 trueboolean[] used;/* 主函数输入一组不重复的数字返回它们的全排列 */public ListListInteger permute(int[] nums) {used new boolean[nums.length];backtrack(nums);return res;}// 回溯算法核心函数void backtrack(int[] nums) {// base case到达叶子节点if (track.size() nums.length) {// 收集叶子节点上的值res.add(new LinkedList(track));return;}// 回溯算法标准框架for (int i 0; i nums.length; i) {// 已经存在 track 中的元素不能重复选择if (used[i]) {continue;}// 做选择used[i] true;track.addLast(nums[i]);// 进入下一层回溯树backtrack(nums);// 取消选择track.removeLast();used[i] false;}}
}
排列问题II(元素可重复但不可复选):
题目描述给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 题目链接47. 全排列 II - 力扣LeetCode
这里我们需要保证相同元素在排列中的相对位置保持不变 什么意思呢比如说 nums [1,2,2] 这个例子我们保持排列中 2 一直在 2 前面又比如 nums [1,2,2,2]我们只要保证重复元素 2 的相对位置固定比如说 2 - 2 - 2也可以得到无重复的全排列结果。我们直接上代码
class Solution {ListListInteger res new LinkedList();LinkedListInteger track new LinkedList();boolean[] used;public ListListInteger permuteUnique(int[] nums) {// 先排序让相同的元素靠在一起Arrays.sort(nums);used new boolean[nums.length];backtrack(nums);return res;}void backtrack(int[] nums) {if (track.size() nums.length) {res.add(new LinkedList(track));return;}for (int i 0; i nums.length; i) {if (used[i]) {continue;}// 新添加的剪枝逻辑固定相同的元素在排列中的相对位置if (i 0 nums[i] nums[i - 1] !used[i - 1]) {continue;}track.add(nums[i]);used[i] true;backtrack(nums);track.removeLast();used[i] false;}}
}与上面的剪枝逻辑有些不同这里多了个!used[i - 1],以 nums [2,2,2]产生的回溯树为例 在满足前面两个条件的情况下我们基本可以断定没有用过的分路也是重复的我们需要将这些枝减掉
排列问题III(元素无重复但可复选):
比如输入 nums [1,2,3]那么这种条件下的全排列共有 3^3 27 种 [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
] 标准的全排列算法利用 used 数组进行剪枝避免重复使用同一个元素。如果允许重复使用元素的话直接放飞自我去除所有 used 数组的剪枝逻辑就行了。
代码详解
class Solution {ListListInteger res new LinkedList();LinkedListInteger track new LinkedList();public ListListInteger permuteRepeat(int[] nums) {backtrack(nums);return res;}// 回溯算法核心函数void backtrack(int[] nums) {// base case到达叶子节点if (track.size() nums.length) {// 收集叶子节点上的值res.add(new LinkedList(track));return;}// 回溯算法标准框架for (int i 0; i nums.length; i) {// 做选择track.add(nums[i]);// 进入下一层回溯树backtrack(nums);// 取消选择track.removeLast();}}
}
最后总结
回溯算法本质就是个多叉树的遍历问题关键就是在前序遍历和后序遍历的位置做一些操作算法框架如下 void backtrack(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {//注意i0,istart的区别处理节点;backtrack(路径选择列表); // 递归 注意(i)和(i)的区别 回溯撤销处理结果}
}
写 backtrack 函数时需要维护走过的「路径」和当前可以做的「选择列表」当触发「结束条件」时将「路径」记入结果集。 最后返回结果集合得到答案。 参考文章「leetcode」最强回溯算法总结篇历时21天、画了20张树形结构图、14道精选回溯题目精讲_回溯负负得正,思维导图-CSDN博客 《labuladong算法笔记》 结语 写博客不仅仅是为了分享学习经历同时这也有利于我巩固自己的知识点总结该知识点由于作者水平有限对文章有任何问题的还请指出接受大家的批评让我改进。同时也希望读者们不吝啬你们的点赞收藏关注你们的鼓励是我创作的最大动力
