（LeetCode 216）组合总和 III [DFS:简单入门 + 去重]

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://blog.csdn.net/STILLxjy/article/details/83627703
“组合总和 II”：https://blog.csdn.net/STILLxjy/article/details/83660387

在经过以上两题之后，这题就非常简单了。
1：自己手动构造一个candidates[1,2,3,4,5,6,7,8,9]
2：使用int size 记录当前组合的大小。

AC代码：

class Solution {
public:
    vector<int> candidates = {1,2,3,4,5,6,7,8,9};
    
    void dfs(vector<int> cur, int sum, int size, int used, vector<vector<int>>& ans, int k, int target)
    {
        if(sum > target) return;
        if(size > k) return;
        if(sum == target && size == k)
        {
            ans.push_back(cur);
            return;
        }
        
        for(int i=used;i<9;i++)
        {
            vector<int> t = cur;
            t.push_back(candidates[i]);
            int s = t.size();
            dfs(t,sum+candidates[i],s,i+1,ans,k,target);
            if(sum+candidates[i] > target) break;
        }
    }
    
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        if(k == 0) return ans;
        vector<int> cur;
        dfs(cur,0,0,0,ans,k,n);
        return ans;
    }
};