原题地址（中等）

代码1

直接使用了weiwei 老哥的思路

class Solution {
public:
    vector<vector<int>> vv;
    vector<int> v;
    void dfs(vector<int> candidates, int k, int cur, int end){
        if(k < 0)  return;
        if(k == 0){
            vv.push_back(v);
            return ;
        }
        // 回溯
        for(int i=cur; i<=end; i++){
            v.push_back(candidates[i]);
            dfs(candidates, k-candidates[i], i, end);
            v.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size();
        if(n==0)    return {};
        dfs(candidates, target, 0, n-1);
        return vv;
    }
};

代码2

自己想出来的。回溯嘛，就是两种情况呗。
遇到当前元素时：

• 把当前元素加入vector，然后继续；
• 不加当前元素，然后继续；

只不过此题有点稍微不同，那就是在加入当前元素之后，还存在两种选择：

1. 继续处理当前元素（因为题目允许元素重复）
2. 处理下一个元素

只不过这个思路和代码1相比，是会产生重复解的，所以我用了set容器。

class Solution {
public:
    set<vector<int>> ans;  // 进行去重
    vector<int> v;
    vector<int> nums;
    void dfs(int k, int cur, int end){
        int sum = 0;
        for(auto num : v)   sum += num;
        //终止条件和减枝
        if(sum == k){
            ans.insert(v);
            return;
        }
        if(cur > end || sum > k || k - sum < nums[cur])  return;
        //递归情况1，加入当前元素
        v.push_back(nums[cur]);
        dfs(k, cur, end);
        dfs(k, cur+1, end);
        //情况2，不加当前元素
        v.pop_back();
        dfs(k, cur+1, end);
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int n = candidates.size();
        nums = candidates;
        dfs(target, 0, n-1);
        vector<vector<int>> vv(ans.begin(), ans.end());
        return vv;
    }
};