combination-sum

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