LeetCode 216. 组合总和 III

LeetCode 216. 组合总和 III

思路：

按照从小到大的顺序去搜索就不会出现重复，如果不是按照start去搜索，递归的dfs还会搜索到前面的数字。

代码：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(1,k,n);
        return res;
    }

    void dfs(int start,int k,int n){
        if(!n){
            if(!k) res.push_back(path);
            return;
        }

        for(int i = start;i <= 9;i++){
            if(n >= i){
                path.push_back(i);
                dfs(i + 1,k - 1,n - i);
                path.pop_back();
            }
        }

    }
};