216.组合总和III题目描述找出所有相加之和为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没有有效的组合。提示:2 k 91 n 60代码classSolution{// 存放最终结果ListListIntegerresultnewArrayList();// 存放当前组合路径ListIntegerpathnewLinkedList();// 当前路径元素总和intsum0;/** * 回溯函数 * * param k 需要选择的数字个数 * param n 目标和 * param startIndex 当前递归开始的位置 */publicvoidbacktracking(intk,intn,intstartIndex){// 剪枝// 当前总和已经大于目标值// 后面继续选择只会更大if(sumn)return;// 终止条件// 当已经选择 k 个数字时if(path.size()k){// 若当前总和等于目标值// 说明找到一个合法组合if(sumn){result.add(newLinkedList(path));}return;}// 横向遍历for(intistartIndex;i9-(k-path.size()-1);i){// 剪枝// 当前 i 选中后// 后面还需要 k - path.size() - 1 个元素// 若剩余元素不足则停止遍历// 1. 做选择path.add(i);sumi;// 2. 递归进入下一层// 下一层从 i1 开始避免重复选择backtracking(k,n,i1);// 3. 回溯撤销选择sum-i;path.removeLast();}}publicListListIntegercombinationSum3(intk,intn){// 从数字 1 开始搜索backtracking(k,n,1);returnresult;}}
LeetCode--216.组合总和III（回溯算法）
发布时间：2026/6/16 1:15:24
216.组合总和III题目描述找出所有相加之和为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没有有效的组合。提示:2 k 91 n 60代码classSolution{// 存放最终结果ListListIntegerresultnewArrayList();// 存放当前组合路径ListIntegerpathnewLinkedList();// 当前路径元素总和intsum0;/** * 回溯函数 * * param k 需要选择的数字个数 * param n 目标和 * param startIndex 当前递归开始的位置 */publicvoidbacktracking(intk,intn,intstartIndex){// 剪枝// 当前总和已经大于目标值// 后面继续选择只会更大if(sumn)return;// 终止条件// 当已经选择 k 个数字时if(path.size()k){// 若当前总和等于目标值// 说明找到一个合法组合if(sumn){result.add(newLinkedList(path));}return;}// 横向遍历for(intistartIndex;i9-(k-path.size()-1);i){// 剪枝// 当前 i 选中后// 后面还需要 k - path.size() - 1 个元素// 若剩余元素不足则停止遍历// 1. 做选择path.add(i);sumi;// 2. 递归进入下一层// 下一层从 i1 开始避免重复选择backtracking(k,n,i1);// 3. 回溯撤销选择sum-i;path.removeLast();}}publicListListIntegercombinationSum3(intk,intn){// 从数字 1 开始搜索backtracking(k,n,1);returnresult;}}
