22ms C++ solution


  • 0
    B
    class Solution {
    public:
        void combinationSum_Recur(vector<vector<int> > &buf, int cur,
            int target, vector<int> &piece, vector<vector<int> > &ans)
        {
            if(cur == target)
            {
                ans.push_back(piece);
            }
            int last = 0;
            if(piece.size()>0)last = piece.back();
            for(int i = 0; i < buf[cur].size(); i ++)
            {
                int step = buf[cur][i];
                if(step < last)break; // the solution must be ascending
                piece.push_back(step);
                combinationSum_Recur(buf, cur + step, target, piece, ans);
                piece.pop_back();
            }
        }
        vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
            vector<vector<int> > ans;
            if(target < 1)return ans;
            int C = candidates.size();
            sort(candidates.begin(), candidates.end());
            vector<vector<int> > buf;
            for(int i = 0; i <= target; i ++)
            {
                buf.push_back(vector<int>());
            }
            for(int i = C-1; i >= 0; i --)
            {
                int step = candidates[i];
                if(target >= step)
                {
                    buf[target - step].push_back(step);
                }
                for(int j = target - 1; j >= step; j --)
                {
                    if(buf[j].size()>0)
                    {
                        buf[j-step].push_back(step);
                    }
                }
            }
            if(buf[0].size()<1)return ans;
            vector<int> piece;
            combinationSum_Recur(buf, 0, target, piece, ans);
            return ans;
        }
    };

Log in to reply
 

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