递归can_sum函数记忆化失效排查：大测试用例运行过慢问题

我正在通过Structy.com的课程学习数据结构与算法，目前在解决sum-possible问题：给定目标和与一组数字数组，判断是否能通过数组中数字的任意组合相加得到目标和。我给实现的can_sum函数加了记忆化优化，但处理大规模测试用例时运行耗时依然很长，说明计算可能没被正确记忆化，或者记忆化结果没按预期被查询。多次检查重写代码都没找到问题，恳请帮忙排查错误。

实现代码 #

def can_sum(target, numbers, memo = {})
  return true if target == 0
  return false if target < 0
  return memo[target] if memo[target]

  numbers.each do |n|
    remainder = target - n
    if can_sum(remainder, numbers, memo) == true
      memo[target] = true
      return true
    end
  end
  
  memo[target] = false
  return false
end

通过的测试用例 #

it "returns true when sum to target is possible from given no's" do
 result = can_sum(7, [2, 3])
 expect(result).to be(true)
end

it "returns true when sum to target is possible from given no's" do
 result = can_sum(7, [5, 3, 4, 7])
 expect(result).to be(true)
end

运行过慢的测试用例 #

it "returns false when sum to target is impossible from given no's" do
 result = can_sum(2017, [4, 2, 10])
 expect(result).to be(false)
end

it "returns false when sum to target is impossible from given no's" do
 result = can_sum(300, [7, 14])
 expect(result).to be(false)
end

核心错误分析 #

你的代码问题出在Ruby默认参数的初始化机制上：memo = {}是在函数定义时就创建了一个哈希对象，而非每次调用函数时生成新的。这意味着所有can_sum调用（包括不同测试用例的调用）都会共享同一个memo哈希。

第一个测试用例运行后，memo中已存储了部分键值对；后续测试用例调用时会复用这个被污染的缓存，导致记忆化逻辑混乱——要么错误命中旧缓存，要么缓存未正确隔离，最终引发递归过程中大量重复计算，表现为大测试用例运行极慢。

修正后的代码 #

将默认参数改为memo = nil，并在函数内部初始化新哈希，确保每次顶层调用都拥有独立的记忆缓存：

def can_sum(target, numbers, memo = nil)
  memo ||= {} # 仅当memo为nil时创建新哈希
  return true if target == 0
  return false if target < 0
  return memo[target] if memo.key?(target) # 用key?判断缓存存在性，避免值为false时的误判

  numbers.each do |n|
    remainder = target - n
    if can_sum(remainder, numbers, memo)
      memo[target] = true
      return true
    end
  end
  
  memo[target] = false
  return false
end

关键修正点 #

1. 默认参数初始化：用memo = nil替代memo = {}，彻底避免哈希共享问题。
2. 缓存存在性检查：用memo.key?(target)替代直接判断memo[target]，逻辑更清晰，避免因缓存值为false导致的误跳过。
3. 缓存隔离：每次顶层调用生成独立memo，递归时传递同一缓存，确保记忆化仅作用于当前问题的计算树。

修正后，大测试用例会快速返回结果，因为记忆化逻辑会正确缓存所有中间状态，彻底避免重复计算。

内容的提问来源于stack exchange，提问作者jbk