題目

找出所有相加之和為 n 的 k 個(gè)數(shù)的組合，且滿(mǎn)足下列條件：

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

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

示例 1:

輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒(méi)有其他符合的組合了。

解

class Solution {public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();dfs(k, 1, n, path, result);return result;}public void dfs(int k, int index, int target, LinkedList<Integer> path, List<List<Integer>> result) {if (target == 0 && path.size() == k) {result.add(new LinkedList<>(path));return;}for (int i = index; i <= 9; i++) {path.add(i);dfs(k, i + 1, target - i, path, result);path.removeLast();}}
}