Easy understand and clear backtracking solution C++


  • 0
    D
    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> res; 
            vector<int> vec_res;
            helper(candidates, target, res, vec_res, 0); 
            return res; 
        }
        void helper(vector<int>& can, int target, vector<vector<int>>& res, vector<int> &vec_res, int begin) {
            if (target == 0) {
                res.push_back(vec_res); 
                return; 
            }
            for (int i = begin; i <= can.size()-1; i++) {
                if (can[i] > target) continue; 
                else {
                    vec_res.push_back(can[i]); 
                    helper(can,target-can[i],res,vec_res,i);
                    vec_res.pop_back(); 
                }
            }
        }
    };
    

  • 0
    H

    @dean2015 Sort "combinationSum" and "if (can[i] > target) return". It's faster.


  • 0
    D

    @HongXu_1994 Great. Thanks!


Log in to reply
 

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