【LeetCode热题100】【回溯】组合总和

class Solution {
public:
    vector<vector<int> > ans;
    vector<int> an;
    vector<int> candidates;
    int target;

    void dfs(int begin, int sum) {
        if (sum == target) {
            ans.push_back(an);
            return;
        } else if (sum > target)
            return;
        for (int i = begin; i < candidates.size(); ++i) {
            sum += candidates[i];
            an.push_back(candidates[i]);
            dfs(i, sum);
            an.pop_back();
            sum -= candidates[i];
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        this->candidates = candidates;
        this->target=target;
        dfs(0, 0);
        return ans;
    }
};