leetcode-cpp/0039.cpp at main · s4nj1th/leetcode-cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
  vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
    vector<vector<int>> res;
    vector<int> comb;
    combos(candidates, target, 0, comb, 0, res);
    return res;
  }

private:
  void combos(vector<int> &candidates, int target, int idx, vector<int> &comb,
              int total, vector<vector<int>> &res) {
    if (total == target) {
      res.push_back(comb);
      return;
    }

    if (total > target || idx >= candidates.size()) {
      return;
    }

    comb.push_back(candidates[idx]);
    combos(candidates, target, idx, comb, total + candidates[idx], res);
    comb.pop_back();
    combos(candidates, target, idx + 1, comb, total, res);
  }
};