面试算法-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();
        }
    }
}