[数据结构与算法][leetcode]216.组合总和（3）

找出所有相加之和为 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]]

思路：dfs+剪枝

基本思想与[leetcode]39.组合总和一致，本题中候选集固定为{1,2,3,4,5,6,7,8,9}，并且固定了答案集合中元素的个数。于是满足条件的答案为sum == target && temp.size() == k，剪枝条件为index == n || sum > target || temp.size() > k。

AC代码：（C++）

class Solution {
   public:
    vector<int> temp;
    void dfs(vector<vector<int>>& ans, vector<int>& candidates, int index, int target, int sum, int k) {
        if (sum == target && temp.size() == k) {
            ans.push_back(temp);
            return;
        }
        if (sum > target || index == candidates.size() || temp.size() > k) {
            return;
        }
        for (int i = index; i < candidates.size() && sum <= target && temp.size() <= k; i++) {
            temp.push_back(candidates[i]);
            dfs(ans, candidates, i + 1, target, sum + candidates[i], k);
            temp.pop_back();  //回溯
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> candidates{1, 2, 3, 4, 5, 6, 7, 8, 9};
        dfs(ans, candidates, 0, n, 0, k);
        return ans;
    }
};