My 34 lines C++ code, DFS and stack struct implement it


  • 0
    H

    class Solution {
    private:
    vector<vector<int>> ret;
    void DFS(vector<int>& a,stack<int>& s,int index,int target){
    if(target==0){
    vector<int> sub_ret;
    stack<int> tmp_s = s;
    while(!tmp_s.empty()){
    sub_ret.push_back(tmp_s.top());
    tmp_s.pop();
    }
    sort(sub_ret.begin(),sub_ret.end());
    ret.push_back(sub_ret);
    }
    else if(target>0){
    for(int i=index;i<a.size();i++){
    s.push(a[i]);
    DFS(a,s,i,target-a[i]);
    }
    }
    s.pop();
    return;
    }
    public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(),candidates.end());
    stack<int> s;
    for(int i=0;i<candidates.size();i++){
    s.push(candidates[i]);
    DFS(candidates,s,i,target-candidates[i]);
    }
    return ret;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.