16 ms c++ Solution, easy-to-understand


  • 1
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> result;
            vector<int> tmp;
            int val = 0;
            //Sort candidates to speed up the computation
            sort(candidates.begin(), candidates.end());
            helper(result, tmp, candidates, val, target, 0);
            return result;
        }
        void helper(vector<vector<int>> &result, vector<int> &tmp, vector<int> &candidates, int val, int target, int start) {
            
            for (int i = start; i < candidates.size(); i++) {
                // Since candidates is sorted, once val + candidates[i] is larger than target, all the following elements do not become the candidate
                if (val + candidates[i] > target) break;
                if (val + candidates[i] == target) {
                    tmp.push_back(candidates[i]);
                    result.push_back(tmp);
                    // Since we use the reference to speed up computation, we need to erase the element we insert to tmp
                    // Comment out 22th line, and remove the & beside tmp, the computation time increases to 20ms
                    tmp.pop_back();
                    break;
                }
                tmp.push_back(candidates[i]);
                helper(result, tmp, candidates, val + candidates[i], target, i);
                tmp.pop_back();
            }
        }
    };

Log in to reply
 

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