题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

样例

输入: k = 3, n = 7
输出: [[1,2,4]]

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

算法分析

dfs

• 1、dfs(k, n, count, u, sum)：k表示只能用k个数，n表示题目给定需要用k个数凑出来的总值，count表示目前用的数的个数，u表示从哪个数开始往下枚举，避免重复，sum表示当前已经凑出来的总值
• 2、如果当前用了数是x，那下一次枚举的位置u就需要从x + 1开始枚举，避免重复操作

时间复杂度 $O(C_{k}^{9}K)$

从9个数中选k个，共有$C_{k}^{9}$个方案，每次记录需要$O(k)$的时间

Java 代码

class Solution {
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static List<Integer> path = new ArrayList<Integer>();
    static void dfs(int k, int n, int count, int u, int sum)
    {
        if(sum > n) return ;
        if(k == count)
        {
            if(sum == n) ans.add(new ArrayList<>(path));
            return ;
        }
        for(int i = u;i <= 9;i ++)
        {
            path.add(i);
            dfs(k, n, count + 1, i + 1, sum + i);
            path.remove(path.size() - 1);
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        ans.clear();
        dfs(k, n, 0, 1, 0);
        return ans;
    }
}