40. Combination Sum II

Same idea as "39. Combination Sum". The only difference is to kick out duplicates.

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

When I revisited this problem, I did following way. I missed line 13 and made mistakes in
Line 22-23: I was trying to push candidates[start] to sol and call “helper(candidates, start+1, sum+candidates[start], target, sol, res)”.

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