題目描述
找出所有相加之和為 n 的 k 個數(shù)的組合，且滿足下列條件：

• 只使用數(shù)字1到9
• 每個數(shù)字 最多使用一次

返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

輸入示例

k = 3, n = 7

輸出示例

[[1,2,4]]

解題思路

解題代碼

class Solution {List<List<Integer>> ans = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public List<List<Integer>> 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) {// 收集結(jié)果ans.add(new ArrayList<Integer>(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, i+1, k);sum -= i;path.removeLast();}}
}