< Back




40. Combination Sum II

Given a list of candidates and a target, target, we're asked to return all combinations of the input
that sum to that target, without duplicates.

Sorting the input helps us avoid creating duplicate combinations as we can avoid traversing paths
with the same starting number. We maintain a running total used to determine if we should select a
path after checking the sum of the current number against the running total - if it's less than the
target we traverse the path.

Once the sum of the combination is equal to the target, we append it to our answer list and
terminate.

The solution is as follows:


  from collections import Counter

  class Solution:
      def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
          ans, n = [], 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):
                  if j > i and candidates[j] == candidates[j - 1]:
                      continue

                  if candidates[j] + t <= target:
                      s.append(candidates[j])
                      backtrack(s, j + 1, t + candidates[j])
                      s.pop()
                  else:
                      return

          backtrack([], 0, 0)

          return ans


_ Time Complexity:

  O(2^n) - We create all possible combinations from the input array in the worst case.

_ Space Complexity:

  O(n) - Where n is the size of the input, this is our recursion stack.