39. Combination Sum

https://leetcode.com/problems/combination-sum/

Python

Recursive

• Remember seem combs with a tuple set

class Solution:
    def __init__(self):
        self.seem = set()

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        return self._travel(candidates, target, [], [])

    def _travel(self, cands, target, wip, combs):
        total = sum(wip)
        if total == target:
            key = tuple(sorted(wip))
            if key not in self.seem:
                self.seem.add(key)
                combs.append(wip)
            return

        if total > target:
            return

        for cand in cands:
            self._travel(cands, target, wip+[cand], combs)
        return combs

Javascript

var combinationSum = function(candidates, target) {
  var result = [];
  var backtrack = function(start, target, record = []) {
    if (target === 0) {
      result.push(record.slice(0))
      return;
    }
    if (target < 0) return;

    for (let i = start; i < candidates.length; i++) {
      const reminder = target - candidates[i];
      if (reminder >= 0) {
        record.push(candidates[i]);
        backtrack(i, reminder, record);
        record.pop();
      }
    }
  }

  backtrack(0, target);
  return result;
};