Elegant Recursive DFS In C++


  • 0
    H
    class Solution {
    public:
      void Search(vector<int> &candidates, int begin, int target, vector<int> &nums,
                  vector<vector<int>> &ret) {
        if (begin >= candidates.size() || target <= 0) {
          if (target == 0) {
            ret.push_back(nums);
          }
          return;
        }
    
        // skip candidates[begin], move to begin + 1.
        Search(candidates, begin + 1, target, nums, ret);
    
        // keep candidates[begin], still process begin.
        nums.push_back(candidates[begin]);
        Search(candidates, begin, target - candidates[begin], nums, ret);
        nums.pop_back();
      }
    
      vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> ret;
        vector<int> nums;
        Search(candidates, 0, target, nums, ret);
        return ret;
      }
    };

Log in to reply
 

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