Dart递归与记忆化实现异常：Null Safety处理求助

我正在学习YouTube热门频道的《Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges》视频教程，教程采用JavaScript实现，我尝试将其中的canSum递归记忆化代码转译为Dart，但代码无法正常运行，尤其在Null Safety处理上存在困惑。

原JavaScript代码 #

const canSum = (targetSum, numbers, memo={}) => {
  if (targetSum in memo) return memo[targetSum];
  if (targetSum === 0) return true;
  if (targetSum < 0) return false;

  for (let num of numbers) {
    const remainder = targetSum - num;
    if (canSum(remainder, numbers, memo) === true) {
      memo[targetSum] = true;
      return true;
      }
    }
  memo[targetSum] = false;
  return false;
};

我转译的Dart代码 #

canSum(targetSum, List<int> array, [Map<int, bool>? memo]) {
  if (memo?.containsKey(targetSum) == true) return memo![targetSum];
  if (targetSum == 0) return true;
  if (targetSum < 0) return false;
  for (int element in array) {
    final difference = targetSum - element;
    if (canSum(difference, array, memo)) {
      (memo ??= {})[targetSum] = true;
      return true;
    }
  }
  (memo ??= {})[targetSum] = false;
  return false;
}

问题分析 #

你的代码存在两个核心问题：

1. 记忆化Map未共享：第一次调用时memo为null，当执行(memo ??= {})会创建新Map，但递归调用传递的仍然是最初的null值，导致每个递归分支都生成独立的Map，完全无法实现缓存复用，这是代码失效的主要原因。
2. 类型与空安全处理不严谨：函数未显式声明返回值类型，Dart会推断为Object?，可能引发调用时的类型错误；memo![targetSum]的强制解包虽然语法合法，但可以通过提前初始化memo来避免不必要的空断言。

解决方案 #

修改后的代码如下，解决了空安全问题并确保记忆化Map在递归中共享：

bool canSum(int targetSum, List<int> array, [Map<int, bool>? memo]) {
  // 初始化memo，确保后续所有递归调用都使用同一个Map
  memo ??= {};

  // 直接使用非null的memo，无需空断言
  if (memo.containsKey(targetSum)) {
    return memo[targetSum]!;
  }

  if (targetSum == 0) return true;
  if (targetSum < 0) return false;

  for (int element in array) {
    final difference = targetSum - element;
    if (canSum(difference, array, memo)) {
      memo[targetSum] = true;
      return true;
    }
  }

  memo[targetSum] = false;
  return false;
}

修改要点说明 #

• 函数开头用memo ??= {}初始化，确保memo始终为非null的Map，所有递归分支共享同一个缓存容器。
• 显式声明返回值类型为bool，避免类型推断带来的潜在问题。
• 因已确保memo非null，memo.containsKey(targetSum)后直接返回memo[targetSum]!是安全的（因为我们只会往memo中存入bool值）。

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