Easy to understand recursion solution. C++


  • 0
    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> ret;
            sort(candidates.begin(), candidates.end());
            vector<int> tmp;
            recur(candidates, target, 0, 0, tmp, ret);
            
            return ret;
        }
        
        void recur(vector<int> &candidates, int &target, int cur, int index, vector<int> &tmp, vector<vector<int>> &ret) {
            if (cur >= target || index >= candidates.size()) {
                if (cur == target) ret.push_back(tmp);
                return;
            }
            recur(candidates, target, cur, index + 1, tmp, ret);
            int t = 0;
            while (cur < target) { // filled with candidates[index] till full of this element.
                ++ t;
                cur += candidates[index];
                tmp.push_back(candidates[index]);
                recur(candidates, target, cur, index + 1, tmp, ret);
            }
            while (t > 0) {
                tmp.pop_back();
                -- t;
            }
        }
    };

Log in to reply
 

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