39. Combination Sum

A classical backtracking solution.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {  
4:      vector<vector<int>> res;  
5:      vector<int> sol;  
6:      sort(candidates.begin(), candidates.end());  
7:      helper(candidates, 0, sol, res, target);  
8:      return res;  
9:    }  
10:    void helper(vector<int> &candidates, int start, vector<int> &sol, vector<vector<int>> &res, int target) {  
11:      if (target == 0) {  
12:        res.push_back(sol);  
13:        return;  
14:      }  
15:      if (candidates[start] > target) return;  
16:      for (int i = start; i < candidates.size(); i++) {  
17:        sol.push_back(candidates[i]);  
18:        helper(candidates, i, sol, res, target-candidates[i]);  
19:        sol.pop_back();  
20:      }  
21:    }  
22:  };