39题是组合数I，和这道题的区别是上一道题的数字是可以无限制重复使用的，这一题呢只能使用给出来的那些数字

    那么我们的问题来了，要怎么样去排除我们的重复答案呢？
    上一道题我们用大于等于back的数才能往下递归，这里除了这个以外，还需要注意的是，这里给出来的数字也可能重复，所以我们就需要在一层里面只用一次这个数字

    1. class Solution {
    2.    vector<vector<int>> res;
    3.    vector<int> v;
    4.    vector<int> candidates;
    5.    void dfs(int remain, int idx)
    6.    {
    7.        if(remain == 0)
    8.        {
    9.            res.push_back(v);
    10.            return;
    11.        }
    12.        if(idx == candidates.size() || remain < 0)
    13.        {
    14.            return;
    15.        }
    16.        for(int i = idx; i < candidates.size(); i++)
    17.        {
    18.            //在一层里面只用一次这个数字
    19.            if(i > idx && candidates[i] == candidates[i - 1]) continue;
    20.            v.push_back(candidates[i]);
    21.            dfs(remain - candidates[i], i + 1);
    22.            v.pop_back();
    23.        }
    24.    }
    25. public:
    26.    vector<vector<int>> combinationSum2(vector<int>& _candidates, int target) {
    27.        candidates = _candidates;
    28.        sort(candidates.begin(), candidates.end());
    29.        dfs(target, 0);
    30.        return res;
    31.    }
    32. };

    第二次写题

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

    第三次写题
    如果和前面一个一样的话就跳过吧。

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