LeetCode 216. 组合总和 III

博主 2 2020-09-12

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路:

代码:

class Solution {
private:
    vector<vector<int> > ans;
    vector<int> temp;
    set<vector<int> > setAns;
    int k;
public:
    // 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
    vector<vector<int> > combinationSum3(int k, int n) {
        this->k = k;
        dfs(1, 0, n);
        for (auto it = setAns.begin(); it != setAns.end(); ++it) {
            ans.push_back(*it);
        }
        return ans;
    }
    // pos代表是否要加上的数字 范围从1~9递增 num表示已经加入临时队列的数字个数
    /// target表示要达到的目标
    void dfs(int pos, int num, int target){
        // cout << "当前判断pos:" << pos << ",当前num:" << num <<endl;
        if (num == k && target == 0) {// 满足条件
            // cout << "满足条件" << endl;
            setAns.insert(temp);
            return;
        }
        
        
        if (num > k ||  pos >= 10) {// 队列数字多于k个 或者 要加上的数字大于等于10了
            // cout << "num > k ||  pos >= 10" << endl;
            // cout << "num:" << num << endl;
            return;
        }
        
        
        if (num == k && target > 0) {
//            cout << "num == k && target > 0" << endl;
            return;
        }
        

        // num < k 选择是否加上当前数字
        // 加上当前数字
        if (pos <= target) {
            // cout << "加上当前数字"<< pos<< ",target:" << target-pos << endl;
            temp.push_back(pos);
            for (int nextNum = pos+1; nextNum <= 10; ++nextNum) {
                dfs(nextNum, num+1, target-pos);
            }
            temp.pop_back();
            
        }
            // 不加上当前数字
        // cout << "不加上当前数字" << pos<< ",target:" << target<< endl;
        dfs(pos+1, num, target);

    }
};