Non recursive c++ solution


  • 0
    B
    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> ret;
            vector<int> r;
            int sz = candidates.size();
            if(sz == 0) {
                return ret;
            }
            sort(candidates.begin(), candidates.end());
            bool done = false;
            vector<int> trycnt(sz, 0);
            int i,j;
            int left = target;
            int curTryPos = sz-1;
            while(!done) {
                if(left % candidates[sz-1] == 0) {
    				trycnt[sz-1] = left / candidates[sz-1];
                    r.clear();
                    for(i=0; i<sz; i++) {
                        for(j=0; j<trycnt[i]; j++) {
                            r.push_back(candidates[i]);
                        }
                    }
                    ret.push_back(r);   
                }
    			// Back trace
                curTryPos = sz-2;
                while(curTryPos >= 0 && left - candidates[curTryPos] < 0) {
                    left += candidates[curTryPos] * trycnt[curTryPos];
                    trycnt[curTryPos] = 0;
                    curTryPos--;
                }
                if(curTryPos < 0) {
                    done = true;
                }
                else {
                    left -= candidates[curTryPos];
                    trycnt[curTryPos]++;
                }
                
            }
            return ret;
        }
    };

Log in to reply
 

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