加起来和为目标值的组合（C++）（DFS）（求组合）_给定一个数组,取任意个数使得大于等于某个数,求有多少组合,c++

题目描述

给出一组候选数\ C C 和一个目标数\ T T，找出候选数中起来和等于\ T T 的所有组合。
\ C C 中的每个数字在一个组合中只能使用一次。

注意：

• 题目中所有的数字（包括目标数\ T T ）都是正整数
• 组合中的数字 (a_1, a_2, … , a_ka1​,a2​,…,ak​) 要按非递增排序 (a_1 \leq a_2 \leq … \leq a_ka1​≤a2​≤…≤ak​).
• 结果中不能包含重复的组合
• 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

示例1

输入

[100,10,20,70,60,10,50],80

返回值

[[10,10,60],[10,20,50],[10,70],[20,60]]

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        if(num.empty())
            return res;
        sort(num.begin(),num.end());
        dfs(num,target,res,tmp,0);       //数组，目标和，res, tmp, 开始的元素下标
        return res;
    }
    void dfs(vector<int> &num, int target, vector<vector<int>> &res, vector<int> &tmp,int start)
    {
        if(target==0){
            res.push_back(tmp);
            return;
        }
        if(start>=num.size()) return;
        for(int i=start;i<num.size();++i){
            if(i>start && num[i]==num[i-1])      //跳过当前重复值
                continue;
            if(num[i]<=target){
                tmp.push_back(num[i]);
                dfs(num,target-num[i],res,tmp,i+1);
                tmp.pop_back();                  //恢复
            }
        }
    }
};