simple C++ recursive method, 12ms


  • 0
    X
    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    		sort(candidates.begin(), candidates.end());
    		return helper(candidates, target, 0);
        }
        vector<vector<int>> helper(vector<int>& candidates, int target, int idx){
    	   vector<vector<int>> result;
               for(int i = idx; i < candidates.size(); i++){
                   if(candidates[i] > target) break;
    	      else if(candidates[i] == target) result.push_back(vector<int>{target});
    	      vector<vector<int>>prev = helper(candidates, target-candidates[i], i);
    	      for(vector<int> vec: prev){
    		vec.push_back(candidates[i]);
    		result.push_back(vec);
    	      }
               }
    	  return result;
           }
    };
    

Log in to reply
 

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