[leetcode] Combination Sum

vector<vector<int> > findcombination(vector<int> valid, int target){
        vector<vector<int> > res;
        int len = valid.size();
        if(len == 0) return res;
        //discard all the values larger than target.
        while(valid.back() > target){
            valid.pop_back();
            if(valid.empty()) return res;

        }
        int i = valid.size() - 1;
        while( i >= 0 ){
            int head = valid[i];
            int cur = head;
            valid.pop_back();
            vector<int> headvec;
            while(cur <= target){
                headvec.push_back(head);
                if(cur == target){
                    res.push_back(headvec);
                    break;
                }
                vector<vector<int> > tails = findcombination(valid, target - cur);
                for(int j = 0; j < tails.size(); ++j){
                    for(int k = 0; k < headvec.size(); ++k){
                        tails[j].push_back(headvec[k]);
                    }
                    res.push_back(tails[j]);
                }
                cur+=head;
            }
            --i;
        }
        return res;
}

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > res;
        if(candidates.empty()) return res;
        sort(candidates.begin(), candidates.end());
        res = findcombination(candidates, target);
        return res;
    }
=========================================================

    void dfs(int left, vector<int>& candidates, vector<int>& current, vector< vector<int> >& ret, int target) {
        if (!target) {ret.push_back(current); return;}
        for (int i = left; i < (int)candidates.size(); ++ i) {
            if (candidates[i] > target) break;
            current.push_back(candidates[i]);
            dfs(i, candidates, current, ret, target - candidates[i]);
            current.pop_back();
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector< vector<int> > ret;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        dfs(0, candidates, current, ret, target);
        return ret;
    }