JZX轻语：简
LeetCode 39 & 216 & 377 - 组合总和相关问题
发表于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]