LeetCode--216.组合总和III（回溯算法）

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个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

代码

classSolution{// 存放最终结果List<List<Integer>>result=newArrayList<>();// 存放当前组合路径List<Integer>path=newLinkedList<>();// 当前路径元素总和intsum=0;/** * 回溯函数 * * @param k 需要选择的数字个数 * @param n 目标和 * @param startIndex 当前递归开始的位置 */publicvoidbacktracking(intk,intn,intstartIndex){// 剪枝：// 当前总和已经大于目标值// 后面继续选择只会更大if(sum>n)return;// 终止条件：// 当已经选择 k 个数字时if(path.size()==k){// 若当前总和等于目标值// 说明找到一个合法组合if(sum==n){result.add(newLinkedList<>(path));}return;}// 横向遍历for(inti=startIndex;i<=9-(k-path.size()-1);i++){// 剪枝：// 当前 i 选中后// 后面还需要 k - path.size() - 1 个元素// 若剩余元素不足，则停止遍历// 1. 做选择path.add(i);sum+=i;// 2. 递归进入下一层// 下一层从 i+1 开始，避免重复选择backtracking(k,n,i+1);// 3. 回溯（撤销选择）sum-=i;path.removeLast();}}publicList<List<Integer>>combinationSum3(intk,intn){// 从数字 1 开始搜索backtracking(k,n,1);returnresult;}}