40_组合总和_II

类型：数组

• 40. 组合总和 II 💛

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

  ❓ 找出数组 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

  💡 回溯

  class Solution:
      def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
          n = len(candidates)
          candidates.sort()
          track = []
          ans = []
  
          def trackback(start):
              if sum(track) == target:
                  ans.append(track[:])
                  return
              if sum(track) > target:
                  return
              if start >= n:
                  return
  
              for i in range(start, n):
                  if i > start and candidates[i] == candidates[i - 1]:
                      continue
                  track.append(candidates[i])
                  trackback(i + 1)
                  track.pop()
  
          trackback(0)
          return ans

  class Solution:
      def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
          def dfs(pos: int, rest: int):
              nonlocal sequence
              if rest == 0:
                  ans.append(sequence[:])
                  return
              if pos == len(freq) or rest < freq[pos][0]:
                  return
  
              dfs(pos + 1, rest)
  
              most = min(rest // freq[pos][0], freq[pos][1])
              for i in range(1, most + 1):
                  sequence.append(freq[pos][0])
                  dfs(pos + 1, rest - i * freq[pos][0])
              sequence = sequence[:-most]
  
          freq = sorted(collections.Counter(candidates).items())
          ans = list()
          sequence = list()
          dfs(0, target)
          return ans

  时间复杂度：O(2^n * n)，空间复杂度：O(n)