易营宝智能建站,sem优化服务公司,wordpress主机要求,做外汇上什么网站看新闻【回溯算法】【回溯算法剪枝】 Leetcode 77.组合 216. 组合总和 III 回溯算法可以解决的问题Leetcode 77.组合解法1 回溯法三部曲#xff0c;函数参数、终止条件和单层搜索逻辑解法一plus 回溯法剪枝 另一道组合回溯问题 216. 组合总和 III解法#xff1a;回溯解法#xff1… 【回溯算法】【回溯算法剪枝】 Leetcode 77.组合 216. 组合总和 III 回溯算法可以解决的问题Leetcode 77.组合解法1 回溯法三部曲函数参数、终止条件和单层搜索逻辑解法一plus 回溯法剪枝 另一道组合回溯问题 216. 组合总和 III解法回溯解法 回溯剪枝 回溯算法可以解决的问题
组合问题N个数里面按一定规则找出k个数的集合 切割问题一个字符串按一定规则有几种切割方式 子集问题一个N个数的集合里有多少符合条件的子集 排列问题N个数按一定规则全排列有几种排列方式 棋盘问题N皇后解数独等等 Leetcode 77.组合 ---------------题目链接-------------------
解法1 回溯法三部曲函数参数、终止条件和单层搜索逻辑 class Solution {ListListInteger result new ArrayList(); // 用于汇总单一结果作为最终结果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){ // 1.确定递归函数的参数和返回值// 2.确定终止条件当最后得到的path的大小等于k 就可以将path存入result中了 终止递归// 注意一下这里把path存进result的时候不能直接存path不然就是浅拷贝最后result中的值都一样if(path.size() k){result.add(new ArrayList(path));return;}// 3. 确定横向的单层搜索逻辑 每次搜索都是从startindex开始startindex保证取过不再取 保证【组合】// for循环用来横向遍历从左到右取数 取过的数字不再取。递归的过程是纵向遍历下一层搜索要从i1开始。// 这里in是因为 数据是范围 [1, n]i就代表了数据而不是索引for(int i startindex; i n; i){ // 控制树的横向遍历path.add(i); // 处理节点将i加入到path路径中backtracking(n,k,i1); // 递归控制树的纵向遍历注意下一层搜索要从startindex i1开始path.removeLast(); // 回溯撤销处理的节点}}
} 注意事项 ⭐️ 注意浅拷贝和深拷贝使用new ArrayList(path) 注意移除ArrayList的最后一个元素方法 path.removeLast() 时间复杂度分析回溯问题的时间复杂度有一个通用公式路径长度×搜索树的叶子数。对于本题它等于 O(k⋅C(n,k) 对于给定的n个元素从中选择k个元素的组合数是C(n, k)。每个组合的平均长度是k即组合中有k个元素 空间复杂度O(k)递归调用栈最大深度为kk为要生成的组合的长度 解法一plus 回溯法剪枝 注意事项 ⭐️ 注意浅拷贝和深拷贝使用new ArrayList(path) 注意移除ArrayList的最后一个元素方法 path.removeLast() 剪枝优化if(n-(i-startindex)k) continue; // 剪枝操作 自己写出来所有的变量就知道了要动手 class Solution {ListListInteger result new ArrayList(); // 用于汇总单一结果作为最终结果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){ // 1.确定递归函数的参数和返回值// 2.确定终止条件当最后得到的path的大小等于k 就可以将path存入result中了 终止递归// 注意一下这里把path存进result的时候不能直接存path不然就是浅拷贝最后result中的值都一样if(path.size() k){result.add(new ArrayList(path));return;}// 3. 确定横向的单层搜索逻辑 每次搜索都是从startindex开始startindex保证取过不再取 保证【组合】// for循环用来横向遍历从左到右取数 取过的数字不再取。递归的过程是纵向遍历下一层搜索要从i1开始。// 这里in是因为 数据是范围 [1, n]i就代表了数据而不是索引for(int i startindex; i n; i){ // 控制树的横向遍历if(n-(i-startindex)k) continue; // 剪枝操作path.add(i); // 处理节点将i加入到path路径中backtracking(n,k,i1); // 递归控制树的纵向遍历注意下一层搜索要从startindex i1开始path.removeLast(); // 回溯撤销处理的节点}}
} 另一道组合回溯问题 216. 组合总和 III
相对于77. 组合 (opens new window)无非就是多了一个限制本题是要找到和为n的k个数的组合而整个集合已经是固定的了[1,…,9]。
本题k相当于树的深度9因为整个集合就是9个数就是树的宽度。
例如 k 2n 4的话就是在集合[1,2,3,4,5,6,7,8,9]中求 k个数 2, n和 4的组合。
解法回溯 遍历求加和sumsumn时若递归深度为k则将当前path加入result if(sum n){if(path.size() k){result.add(new ArrayList(path)); // 注意新建ArrayList赋值}return; // 如果path.size() k 但sum ! targetSum 直接返回
}之后进行回溯sum回溯path回溯 class Solution {ListListInteger result new ArrayList();ListInteger path new ArrayList();int sum 0;public ListListInteger combinationSum3(int k, int n) {backtracking(k,n,1);return result;}public void backtracking(int k, int n, int startindex){// 终止条件if(sum n){if(path.size() k){result.add(new ArrayList(path));}return;}for(int i startindex; i 9; i){path.add(i);sum i;backtracking(k,n,i1);sum - path.get(path.size()-1); // 回溯//sum - i; // 回溯 这个方法也行path.removeLast(); // 回溯}}
}解法 回溯剪枝 class Solution {ListListInteger result new ArrayList();ListInteger path new ArrayList();int sum 0;public ListListInteger combinationSum3(int k, int n) {backtracking(k,n,1);return result;}public void backtracking(int k, int n, int startindex){// 终止条件if(sum n) return; // 剪枝 如果sum已经大于n了那就returnif(sum n){if(path.size() k){result.add(new ArrayList(path));}return;}for(int i startindex; i 9; i){path.add(i);sum i;backtracking(k,n,i1);sum - i; // 回溯path.removeLast(); //回溯}}
}
