力扣-39题 组合总和（C++）- 回溯+有价值

题目链接：https://leetcode-cn.com/problems/combination-sum/
题目如下：

class Solution {
public:
    //深搜（搜索回溯）
    vector> ans;
    vector cur;

    vector> combinationSum(vector& candidates, int target) {

        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);

        return ans;
    }

    //表示当前在candidates数组的第start位，还剩target要组合，已经组合的列表为ans
    void dfs(vector& candidates,int target,int start){
        if(target==0){//满足要求，则放入结果中，并返回
            ans.push_back(cur);
            return ;
        }

        for(int i=start;itarget) break;//已排序，若>target，则直接跳出此次遍历，否则，就放入当前cur中
            else cur.push_back(candidates[i]);

            dfs(candidates,target-candidates[i],i);//从当前位置重新开始dfs，因为每个数字可以重复被选取
            cur.pop_back();//此时，弹出当前cur位置，继续下一个位置
        }
    }
};