Combination Sum LeetCode solution in C++

1
class Solution {
2
  void combination(vector<int> &candidates, int target, vector<int> currComb, int currSum,
3
                   int currIndex, vector<vector<int>> &ans) {
4
    if (currSum > target) return; // backtrack
5
    if (currSum == target) {
6
      ans.push_back(currComb); // store the solution and backtrack
7
      return;
8
    }
9

10
    for (int i = currIndex; i < candidates.size();
11
         i++) {                          // try all possible options for the next level
12
      currComb.push_back(candidates[i]); // put 1 option into the combination
13
      currSum += candidates[i];
14
      combination(candidates, target, currComb, currSum, i,
15
                  ans);    // try with this combination, whether it gives a
16
                           // solution or not.
17
      currComb.pop_back(); // when this option backtrack to here, remove this
18
                           // and go on to the next option.
19
      currSum -= candidates[i];
20
    }
21
  }
22

23
 public:
24
  vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
25
    vector<vector<int>> ans;
26
    vector<int> currComb;
27
    combination(candidates, target, currComb, 0, 0, ans);
28
    return ans;
29
  }
30
};