网站中的图片展示功能该设计什么,口碑营销的特点,织梦网站模板官网,怎样做网站卖网站216.组合总和III
216. 组合总和 III - 力扣#xff08;LeetCode#xff09;
代码随想录 (programmercarl.com)
和组合问题有啥区别#xff1f;回溯算法如何剪枝#xff1f;| LeetCode#xff1a;216.组合总和III_哔哩哔哩_bilibili 找出所有相加之和为 n 的 k 个数的组…216.组合总和III
216. 组合总和 III - 力扣LeetCode
代码随想录 (programmercarl.com)
和组合问题有啥区别回溯算法如何剪枝| LeetCode216.组合总和III_哔哩哔哩_bilibili 找出所有相加之和为 n 的 k 个数的组合且满足下列条件 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。 示例 1: 输入: k 3, n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。 示例 2: 输入: k 3, n 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 2 6 9
1 3 5 9
2 3 4 9
没有其他符合的组合了。 示例 3: 输入: k 4, n 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。 第一反应和昨天的77.组合的解法相同不过对于剪枝部分以及n和k怎么应用我还是有点不懂。
看了卡哥的题解发现自己对于题目的理解还是有些偏差。首先该题题意可以理解为在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。K相当于树的深度。
回溯三部曲
1、确定参数和返回值一个一维数组path来存放符合条件的结果一个二位数组result来存放结果集
ListListInteger result new ArrayList(); // 用于存储最终结果的列表
LinkedListInteger path new LinkedList(); // 用于存储当前组合的列表
还需要的参数有n,k,path路径中元素的综合sum下一层for循环搜索的起始位置startIndex:
private void backTracking(int targetSum, int k, int startIndex, int sum) {}
2、确定终止条件path.size和k相等的时候终止sum和targetSum相等的时候用result收集当前结果
if (path.size() k) {if (sum targetSum) result.add(new ArrayList(path));return;
}
3、单层搜索的过程 for (int i startIndex; i 9 ; i) {path.add(i); // 将当前数字加入组合列表sum i; // 更新累加和backTracking(targetSum, k, i 1, sum); // 递归搜索下一个数字path.removeLast(); // 回溯移除最后加入的数字以便尝试其他可能的数字sum - i; // 回溯减去移除的数字恢复累加和
} 剪枝
1、已选元素的值已经大于总和就没有必要再往后遍历了
2、for循环的位置可以剪枝i 9 - (k - path.size()) 1就可以了。
综合代码
class Solution {ListListInteger result new ArrayList(); // 用于存储最终结果的列表LinkedListInteger path new LinkedList(); // 用于存储当前组合的列表public ListListInteger combinationSum3(int k, int n) {backTracking(n, k, 1, 0); // 调用回溯算法寻找符合条件的组合return result; // 返回最终结果}private void backTracking(int targetSum, int k, int startIndex, int sum) {// 减枝如果当前累加的和已经大于目标值则停止当前路径的搜索if (sum targetSum) {return;}// 如果当前组合的元素数量已经达到要求且当前累加和等于目标值将当前组合加入结果列表if (path.size() k) {if (sum targetSum) result.add(new ArrayList(path));return;}// 减枝根据剩余可用数字的数量和目标组合元素数量确定可用的起始数字范围for (int i startIndex; i 9 - (k - path.size()) 1; i) {path.add(i); // 将当前数字加入组合列表sum i; // 更新累加和backTracking(targetSum, k, i 1, sum); // 递归搜索下一个数字path.removeLast(); // 回溯移除最后加入的数字以便尝试其他可能的数字sum - i; // 回溯减去移除的数字恢复累加和}}
}17.电话号码的字母组合 17. 电话号码的字母组合 - 力扣LeetCode 代码随想录 (programmercarl.com) 还得用回溯算法| LeetCode17.电话号码的字母组合_哔哩哔哩_bilibili 有了上一题的基础和思路之后明白这一题要用回溯也知道树怎么画但是对于代码怎么实现还是有些不太明白。 看了卡哥视频题解 从图中可以看出遍历的深度就是【2、3】数组的长度叶子节点就是我们要收集的结果。
回溯三部曲
1、确定参数全局变量一个字符串S手机叶子节点的结果然后用一个字符串数组result把结果收集起来局部变量string digits和index,index用来遍历digits的同时记录遍历到digits的第几个数字
2、确定终止条件indexdigits.size
3、确定单层遍历的逻辑取index指向的数字取该数字对应的字母提前把index中的数字和其对应的字母集用map存储起来
综合代码
class Solution {// 设置全局列表存储最后的结果ListString list new ArrayList();// 主函数传入数字字符串返回所有可能的字母组合public ListString letterCombinations(String digits) {if (digits null || digits.length() 0) {return list; // 如果输入为空则直接返回结果列表}// 初始对应所有的数字为了直接对应2-9新增了两个无效的字符串String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};// 迭代处理backTracking(digits, numString, 0);return list;}// 每次迭代获取一个字符串所以会设计大量的字符串拼接所以这里选择更为高效的 StringBuilderStringBuilder temp new StringBuilder();// 比如 digits 如果为 23num 为 0则 str 表示 2 对应的 abcpublic void backTracking(String digits, String[] numString, int num) {// 遍历全部一次记录一次得到的字符串if (num digits.length()) {list.add(temp.toString()); // 当数字索引已经达到 digits 字符串的长度时将当前拼接好的字符串加入结果列表return;}// str 表示当前 num 对应的字符串String str numString[digits.charAt(num) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i)); // 将当前字符追加到临时 StringBuilder 中backTracking(digits, numString, num 1); // 递归调用处理下一个数字temp.deleteCharAt(temp.length() - 1); // 剔除末尾的字符为下一个迭代做准备}}
}
