设计云网站,wordpress购买按钮插件,沈阳最新通告,重庆网站设计开发文章目录 1.什么是回溯算法2.回溯算法解题步骤3.回溯算法解决组合问题4.回溯算法解决排列问题 1.什么是回溯算法 回溯算法是一种通过尝试所有可能的解决方案来解决问题的算法策略#xff0c;它通常用于求解组合优化、排列组合、路径搜索等类型的问题,是一种暴力求解的算法。 2… 文章目录 1.什么是回溯算法2.回溯算法解题步骤3.回溯算法解决组合问题4.回溯算法解决排列问题 1.什么是回溯算法 回溯算法是一种通过尝试所有可能的解决方案来解决问题的算法策略它通常用于求解组合优化、排列组合、路径搜索等类型的问题,是一种暴力求解的算法。 2.回溯算法解题步骤
回溯算法是一种选优搜索法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法而满足回溯条件的某个状态的点称为 “回溯点”。
回溯算法的解题步骤如下
路径记录已经做过的选择。选择列表当前可以做出的选择。结束条件到达决策树的底层无法再做选择的条件。
回溯算法中最经典的就是组合和排列问题。
3.回溯算法解决组合问题
组合的定义 从 n 个不同元素中取出 m个元素组成一组不考虑元素的顺序这样的一组元素就叫做从 n 个不同元素中取出 m 个元素的一个组合。 题目来自于https://leetcode.cn/problems/combinations/description/
题目描述 给定两个整数 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 4,k2时我们需要在[1,4]之间取出两个数组合 用暴力求解的思想我们很容易想到可以用两成for循环去做但这题的n和k是动态的想要控制好循环的层数还是挺难的。 这个时候就需要使用到回溯算法了先来看以下代码
class Solution {public ListListInteger result new ArrayList();public ListInteger path new ArrayList();public ListListInteger combine(int n, int k) {backTracking(n,k,1);return result;}public void backTracking(int n,int k,int startIndex){if(path.size() k){result.add(new ArrayList(path));return;}for(int i startIndex;i n-(k-path.size())1;i){path.add(i);backTracking(n,k,i1);path.removeLast();}}
}图解上述代码流程
result用于存储最终的所有组合结果是一个二维列表每个子列表代表一个组合。path用于存储路径上的值。
在循环过程中
首先将当前数字 i 添加到 path 中。递归调用 backTracking 方法继续生成下一个数字的组合起始索引更新为 i 1。满足终止条件就收集数据返回到上一次递归中进行回溯。回溯操作将最后添加的数字从 path 中移除以便尝试其他可能的组合。
循环条件中的i n-(k-path.size())1是为了剪枝。 来看一种极端情况假设n 4,k 4. 那么除了一开始的[1,2,3,4]其它情况都没必要遍历。在添加i n-(k-path.size())1这个条件后刚开始执行backTracking我们就保证了i是小于等于1的比1大的情况组合的结果个数都小于4。
4.回溯算法解决排列问题
排列定义 从 n 个不同元素中取出 m 个元素按照一定的顺序排成一列叫做从 n 个不同元素中取出 m 个元素的一个排列。当 n m 时称为全排列。 题目来自https://leetcode.cn/problems/permutations/description/ 给定一个不含重复数字的数组 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来分析 这一题其实和第一题类似上一题的for循环要从当前位置的下一个位置开始而这一题需要从头开始遍历并且不能等于当前的值。 代码如下所示
class Solution {public ListListInteger result new ArrayList();public ArrayListInteger path new ArrayList();public ListListInteger permute(int[] nums) {backTracking(nums);return result;}public void backTracking(int[] num){if(path.size() num.length){result.add(new ArrayList(path));return;}for(int i 0;i num.length;i){if(path.contains(num[i])){continue;}path.add(num[i]);backTracking(num);path.remove(path.size()-1);}}
}只需要更改终止条件并且在for循环中跳过path中包括的值即可。
