< Back




39. Combination Sum

We're given a list of distinct integers, candidates, and asked to find all combinations that sum to
target. The number can be repeated in a particular combination, however, the frequency of the number
should be distinct across combinations.

We use backtracking to construct our combinations, and we maintain a running total as well as the
current index to construct the next combination from. During our recursion, if the running total is
equal to the target, we append the current combination to the answer list and return.

If the current number we're considering plus the running total is less than or equal to the target,
we add it to the running total and continue our recursion. Otherwise, we return immediately. Why?
Because of the time complexity of combinations in general, it won't cost us much to also sort the
input candidates prior to backtracking. So if the current number in the sorted input list plus the
running total is greater than the target, we know all future numbers will also be greater than the
target. Therefore, we terminate recursion for this path immediately.

The solution is as follows:


  class Solution:
      def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
          n, ans = len(candidates), []
          candidates.sort()

          def backtrack(s: List[int], i: int, t: int) -> None:
              if t == target:
                  ans.append(s[:])
                  return

              for j in range(i, n):
                  num = candidates[j]

                  if t + num <= target:
                      s.append(num)
                      backtrack(s, j, t + num)
                      s.pop()
                  else:
                      return

          backtrack([], 0, 0)

          return ans


_ Time Complexity:

  O(n^(t/m + 1)) - n is the number of candidates, t is the target value, and m is the minimum value
  among the candidates.

_ Space Complexity:

  O(t/m) - The recursion stack will have at most t/m frames.