class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) 
    {
        //sort candidates
        int size=candidates.size();
        for(int i=0;i<size;i++)
            for(int j=i+1;j<size;j++)
                if(candidates[i]>candidates[j])
                {
                    int tmp=candidates[i];
                    candidates[i]=candidates[j];
                    candidates[j]=tmp;
                }
        //dfs
        vector<vector<int>> result;
        if(size==0) return result;
        
        int v[target/candidates[0]];
        int cdep=0;
        int vdep=0;
        dfs(result,candidates,size,v,cdep,vdep,target);
        return result;
    }
    
    void dfs(vector<vector<int>>& result,vector<int> &candidates,int& csize,int* v,int& cdep,int& vdep,int& target)
    {
        if(target==0)
        {
            vector<int> vals;
            for(int i=0;i<vdep;i++)
                vals.push_back(v[i]);
            result.push_back(vals);
            return;
        }
        if(cdep==csize || target<candidates[cdep]) return;
        
        int dup=target/candidates[cdep];
        for(int i=0;i<=dup;i++)
        {
            //add to v
            for(int j=0;j<i;j++) v[vdep+j]=candidates[cdep];
            //search next candidate
            target=target-i*candidates[cdep];
            cdep=cdep+1;
            vdep=vdep+i;
            dfs(result,candidates,csize,v,cdep,vdep,target);
            vdep=vdep-i;
            cdep=cdep-1;
            target=target+i*candidates[cdep];
        }
    }
};