防城港网站设计,楼市最新消息:2023年房价走势,济南做网站哪家便宜,网店推广网站题目描述 找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c;组合可以以任何顺序返回。
输入示例
k 3, n 7输出示例
[[1,2,…题目描述 找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
输入示例
k 3, n 7输出示例
[[1,2,4]]解题思路
解题代码
class Solution {ListListInteger ans new ArrayList();DequeInteger path new ArrayDeque();public ListListInteger combinationSum3(int k, int n) {backtrack(n, 0, 1, k);return ans;}public void backtrack(int targetSum, int sum, int begin, int k) {// 剪枝if(sum targetSum) {return;}// 终止条件if(path.size() k) {// 判断是否满足条件if(targetSum sum) {// 收集结果ans.add(new ArrayListInteger(path));return;}}// 剪枝9 - (k - path.size()) 1for(int i begin; i 9 - (k - path.size()) 1; i) {path.addLast(i);sum i;backtrack(targetSum, sum, i1, k);sum - i;path.removeLast();}}
}
