leetcode--216--组合总和 III

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

说明：

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

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

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

题目链接：https://leetcode-cn.com/problems/combination-sum-iii

思考：
1、这道题可以用深度优先搜索dfs来解，dfs的方法主要在于3点：第一，终止条件；第二循环调用；第三，变化条件
2、对应到这个题中，计算和为n的k个数，k个数用完了就是终止了；循环条件是 不断调用下一个dfs，且其中用到的数组值是当前数组值+1；变化条件就是 和n在不断减少，k也在不断减少；具体变现形式见代码

C++代码

class Solution {
    // 所有相加之和为 n 的 k 个数的组合
    // dfs 回溯 + 剪枝

    vector<vector<int>> ret;
    vector<int> curr;

    void dfs(int k, int n, int i){
        if(n<0){
            return;
        }
        if(k==0){
            if (n==0){
                ret.push_back(curr);
            }
            return ;
        }
        for(int j=i+1; j<=9; j++){
            curr.push_back(j);
            dfs(k-1,n-j,j);
            curr.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 0);
        return ret;
    }
};  

Python代码：

class Solution(object):

    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        ret = []
        def dfs(k, n, i, curr):

            if n<0:
                return
            if k==0:
                if n==0:
                    ret.append(curr)
                return 

            for j in range(i+1, 10):
                dfs(k-1, n-j, j, curr+[j])
    
        dfs(k,n,0,[])

        return ret