66. Combination Sum

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res, path = [], []
        def backtrack(start, remain):
            if remain == 0:
                res.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] <= remain:
                    path.append(candidates[i])
                    backtrack(i, remain - candidates[i])   # i, not i+1: reuse allowed
                    path.pop()
        backtrack(0, target)
        return res

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int[] c, int start, int remain, List<Integer> path, List<List<Integer>> res) {
        if (remain == 0) { res.add(new ArrayList<>(path)); return; }
        for (int i = start; i < c.length; i++) {
            if (c[i] > remain) continue;
            path.add(c[i]);
            backtrack(c, i, remain - c[i], path, res);   // i: reuse allowed
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    void backtrack(vector<int>& c, int start, int remain, vector<int>& path, vector<vector<int>>& res) {
        if (remain == 0) { res.push_back(path); return; }
        for (int i = start; i < (int)c.size(); i++) {
            if (c[i] > remain) continue;
            path.push_back(c[i]);
            backtrack(c, i, remain - c[i], path, res);   // i: reuse allowed
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, 0, target, path, res);
        return res;
    }
};

function combinationSum(candidates, target) {
  const res = [], path = [];
  const backtrack = (start, remain) => {
    if (remain === 0) { res.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remain) continue;
      path.push(candidates[i]);
      backtrack(i, remain - candidates[i]); // i: reuse allowed
      path.pop();
    }
  };
  backtrack(0, target);
  return res;
}