这道题和78题，90题 求子集有几分相似，因为返回的结果都是组合数，但是这道题和78,90题的区别是，78题90题里面给出的数字是最多用一次的，这道题不同，给出的数字可能使用很多次。

    对于这种不知道要求和多少次的，最适合用dfs来求解，让它自己去想要递归多少次，我们只要给出来停止条件就好了。
    停止条件就是累加之后的结果正好等于target,又或者累加起来已经超过target了那这个就是个错误答案可以抛弃。

    我们怎么样让结果不重复？
    首先问一个问题：为什么会重复？
    【2，2，3】 【3，2，2】这样就重复了
    怎么出现的？ 因为后面的3再次用到了2
    那么我们可以这样做：先把可选的数字从小到大排序，在寻找答案的过程中每次添加一个数字都只能添加大于等于它本身的

    1. class Solution {
    2.    vector<vector<int>> res;
    3.    vector<int> candidates;
    4.    vector<int> v;
    5.    void dfs(int remain, int last)
    6.    {
    7.        if(remain == 0)
    8.        {
    9.            res.push_back(v);
    10.            return;
    11.        }
    12.        if(remain < 0)
    13.            return;
    14.        // int l =  v.size() - 1;
    15.        for(int i = last; i < candidates.size(); i++)
    16.        {
    17.            v.push_back(candidates[i]);
    18.            dfs(remain - candidates[i], i);
    19.            v.pop_back();
    20.        }
    21.    }
    22. public:
    23.    vector<vector<int>> combinationSum(vector<int>& _candidates, int target) {
    24.        candidates = _candidates;
    25.        sort(candidates.begin(), candidates.end());
    26.        dfs(target, 0);
    27.        return res;
    28.    }
    29. };

    第二种写法：减少参数

    class Solution {
   vector<vector<int>> res;
   vector<int> candidates;
   vector<int> v;
   void dfs(int remain)
   {
       if(remain == 0)
       {
           res.push_back(v);
           return;
       }
       if(remain < 0)
           return;
       // int l =  v.size() - 1;
       for(auto x: candidates)
       {
           // cout << v[l];
           if(v.size() == 0 || x >= v.back())
           {
               v.push_back(x);
               dfs(remain - x);
               v.pop_back();
           }
       }
   }
public:
   vector<vector<int>> combinationSum(vector<int>& _candidates, int target) {
       candidates = _candidates;
       sort(candidates.begin(), candidates.end());
       dfs(target);
       return res;
   }
};

    第二次写题

    class Solution {
    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int>& candidates, int remain)
    {
        if(remain == 0)
        {
            res.push_back(path);
            return;
        }
        for(int i = 0; i < candidates.size(); i++)
        {
            if(candidates[i] <= remain && (!path.size() || (path.size() && candidates[i] >= path.back())))
            {
                path.push_back(candidates[i]);
                dfs(candidates, remain - candidates[i]);
                path.pop_back();
            }
        }
        return;
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target);
        return res;
    }
};

    第三次写题
    这里用到了一个idx，是用来看标记能放哪一个idx的。

    class Solution {
    vector<int> candidates;
    vector<vector<int>> res;
    vector<int> path;
    void dfs(int target, int idx)
    {
        if(target == 0)
        {
            res.push_back(path);
        }
        if(target < 0) return;
        for(int i = idx; i < candidates.size(); i++)
        {
            if(candidates[i] > target) return;
            path.push_back(candidates[i]);
            dfs(target - candidates[i], i);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& _candidates, int target) {
        candidates = _candidates;
        sort(candidates.begin(), candidates.end());
        dfs(target, 0);
        return res;
    }
};