发表于 2024.04.22

• 这三天的每日一题都是组合总和的问题：

  • 第一天的题目39可以用回溯法解决，在参数中记录当前回溯的数组开始位置（由于重复选取，下一次回溯的数组开始位置可以和本次相同）、当前所选用的数字组合arr及其和cur_sum = sum(arr)。如果当前的cur_sum等于target，则加入到结果列表中并返回。为了加快搜寻，如果下一次回溯的cur_sum已经大于target，则直接剪枝。

  • 第二天的题目216同样也是回溯法，由于不能重复选择，则下一次回溯的数组需要从下一个位置开始遍历。如果当前所选用的数字组合长度恰好为k，则加入到结果列表中并返回。同理，可以采用多个剪枝的方法：如果当前选用数字的总和大于等于n，则提前返回；如果直接选用1 - k都大于n，或者直接选用(9 - k + 1) - 9都小于n，则直接返回空数组。

  • 第三天的题目377则使用的是dp，使用dp[i]表示nums中能凑成和为i的元素组合个数。则状态转移方程可以写为dp[i] = sum(dp[i - num] for num in nums if i - num >= 0)(选用数字num，将状态递归到子问题target = i - num的搜寻中)。

  题目39的做法：

  class Solution:
      def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
          ans = []
  
          def backtrack(cur_pos: int, arr: List[int], cur_sum: int):
              nonlocal candidates, ans
              if cur_sum == target:
                  ans.append(list(arr))
              for next_pos in range(cur_pos, len(candidates)):
                  next_sum = cur_sum + candidates[next_pos]
                  if next_sum > target:
                      break
                  arr.append(candidates[next_pos])
                  backtrack(next_pos, arr, next_sum)
                  arr.pop()
          
          candidates.sort()
          backtrack(0, [], 0)
          return ans

  题目216的做法：

  class Solution:
      def combinationSum3(self, k: int, n: int) -> List[List[int]]:
          ans = []
          if (1 + k) * k // 2 > n:
              return ans
  
          def backtrace(cur_num: int, cur_sum: int, cur_arr: List[int]):
              nonlocal k, n
              if len(cur_arr) == k:
                  if cur_sum == n:
                      ans.append(list(cur_arr))
                  else:
                      return
              if cur_sum >= n:
                  return
              for next_num in range(cur_num + 1, n + 1):
                  cur_arr.append(next_num)
                  backtrace(next_num, cur_sum + next_num, cur_arr)
                  cur_arr.pop()
  
          backtrace(0, 0, [])
          return ans

  题目377的做法：

  class Solution:
      def combinationSum4(self, nums: List[int], target: int) -> int:
          dp = [0] * (target + 1)
          dp[0] = 1
          for sum_ in range(1, target + 1):
              for num in nums:
                  if sum_ - num >= 0:
                      dp[sum_] += dp[sum_ - num]
          return dp[target]

• LC