组合求和问题中，how_sum函数的核心需求是：给定一个正整数目标和target_sum，以及一个正整数数组numbers，判断能否从数组中选取若干元素（可重复选取），使得它们的和等于target_sum，如果能则返回其中一种组合方案，不能则返回None。普通的递归实现会存在大量重复子问题的计算，时间复杂度会随着目标值的增大呈指数级上升，而记忆化技术可以通过缓存已经计算过的子问题结果，大幅降低计算开销。
普通递归实现的缺陷
我们先来看没有记忆化的普通递归实现，递归的核心逻辑是：如果当前目标值等于0，说明找到了组合，返回空数组；如果当前目标值小于0，说明当前路径不可行，返回None；否则遍历数组中的每个元素，用当前目标值减去该元素得到新的目标值，递归调用函数，如果递归返回结果不为None，就把当前元素加入结果数组返回。
def how_sum(target_sum, numbers):
# 基线条件：目标和为0，返回空数组表示找到组合
if target_sum == 0:
return []
# 目标和为负，当前路径不可行
if target_sum < 0:
return None
# 遍历数组中的每个元素
for num in numbers:
remainder = target_sum - num
result = how_sum(remainder, numbers)
# 如果子问题有解，把当前元素加入结果
if result is not None:
return result + [num]
# 所有路径都不可行，返回None
return None
这种实现的问题在于，同一个remainder值会被反复计算多次。比如目标值是7，数组是[2,3]，计算how_sum(7,[2,3])的时候，会先算how_sum(5,[2,3])，再算how_sum(4,[2,3])，而how_sum(5,[2,3])内部又会计算how_sum(3,[2,3])、how_sum(2,[2,3])，后续其他分支也会重复计算这些子问题，当目标值较大时，计算量会急剧增加。
添加记忆化的实现方式
记忆化的核心思路是用一个字典（或者数组）缓存已经计算过的target_sum对应的结果，每次递归前先检查缓存中是否有该target_sum的结果，如果有直接返回，不需要重复计算；如果缓存中没有，先计算得到结果，再把结果存入缓存后返回。
步骤1：定义缓存结构
我们可以使用一个字典作为缓存，键是target_sum的值，值是该target_sum对应的how_sum结果，初始化时缓存为空。
步骤2：修改递归逻辑加入缓存判断
在递归函数的开头，先判断当前target_sum是否在缓存中，如果在直接返回缓存值；递归计算得到结果后，先把结果存入缓存，再返回结果。
完整的带记忆化的how_sum函数实现如下：
def how_sum(target_sum, numbers, memo={}):
# 先检查缓存中是否有当前目标值的结果
if target_sum in memo:
return memo[target_sum]
# 基线条件：目标和为0，返回空数组
if target_sum == 0:
return []
# 目标和为负，当前路径不可行
if target_sum < 0:
return None
# 遍历数组中的每个元素
for num in numbers:
remainder = target_sum - num
result = how_sum(remainder, numbers, memo)
# 如果子问题有解，把当前元素加入结果
if result is not None:
memo[target_sum] = result + [num]
return memo[target_sum]
# 所有路径都不可行，缓存None结果并返回
memo[target_sum] = None
return None
两种实现的性能对比
我们可以通过测试不同目标值的运行时间，来直观看到记忆化的优化效果。测试代码如下：
import time
# 普通递归版本
def how_sum_normal(target_sum, numbers):
if target_sum == 0:
return []
if target_sum < 0:
return None
for num in numbers:
remainder = target_sum - num
result = how_sum_normal(remainder, numbers)
if result is not None:
return result + [num]
return None
# 带记忆化版本
def how_sum_memo(target_sum, numbers, memo={}):
if target_sum in memo:
return memo[target_sum]
if target_sum == 0:
return []
if target_sum < 0:
return None
for num in numbers:
remainder = target_sum - num
result = how_sum_memo(remainder, numbers, memo)
if result is not None:
memo[target_sum] = result + [num]
return memo[target_sum]
memo[target_sum] = None
return None
# 测试数据
target = 300
nums = [7, 14]
# 测试普通递归
start = time.time()
print(how_sum_normal(target, nums))
end = time.time()
print(f"普通递归耗时：{end - start:.4f}秒")
# 测试记忆化递归
start = time.time()
print(how_sum_memo(target, nums))
end = time.time()
print(f"记忆化递归耗时：{end - start:.4f}秒")
运行上述代码可以看到，普通递归计算target为300、数组为[7,14]的场景时，会运行很长时间甚至无法得到结果，因为7和14都是7的倍数，永远无法组合出300，普通递归会遍历所有可能的组合路径，计算量极大；而记忆化版本几乎瞬间就能返回None，因为所有计算过的remainder都会被缓存，每个子问题只会计算一次。
实现时的注意事项
- 缓存的键必须是不可变类型，这里target_sum是整数，符合字典键的要求，如果子问题的参数是数组，需要先把数组转为元组再作为缓存键。
- 当递归返回None时，也需要把None存入缓存，避免后续重复计算同一个不可行的target_sum。
- 如果是在类方法中实现记忆化，不要使用默认参数为空字典，因为Python的默认参数是函数定义时创建的，会被所有调用共享，可能导致缓存混乱，建议在函数内部初始化缓存。
通过上述实现，我们就可以正确完成带记忆化的how_sum组合求和递归函数，既保证了结果的正确性，又大幅提升了函数的执行效率，这种记忆化的思路也可以应用到其他类似的递归问题中。