216.组合总和-iii.cpp

/*
 * @lc app=leetcode.cn id=216 lang=cpp
 *
 * [216] 组合总和 III
 *
 * https://leetcode-cn.com/problems/combination-sum-iii/description/
 *
 * algorithms
 * Medium (68.74%)
 * Likes:    66
 * Dislikes: 0
 * Total Accepted:    8.9K
 * Total Submissions: 13K
 * Testcase Example:  '3\n7'
 *
 * 找出所有相加之和为 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]]
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>>ans;
    void CB(int start, int target, int k, vector<int>sub){
        if(k == 0){
            if(target == 0) ans.push_back(sub);
            return;
        }
        for(int i=start; i<=9 && i<=target; i++){
            sub.push_back(i);
            CB(i+1, target-i, k-1, sub);
            sub.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        CB(1, n, k, vector<int>{});
        return ans;
    }
};

// @lc code=end