面试算法-117-组合总和 III

题目

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

解

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();}}
}