本文详解如何在 Java 中为「组合总和」递归解法正确实现记忆化（memoization），重点解决因浅拷贝 List 导致的 memo 值被后续修改、结果错乱的核心陷阱，并提供可直接运行的深拷贝解决方案。
本文详解如何在 java 中为「组合总和」递归解法正确实现记忆化（memoization），重点解决因浅拷贝 `list>` 导致的 memo 值被后续修改、结果错乱的核心陷阱，并提供可直接运行的深拷贝解决方案。
在使用递归求解「所有组合总和等于 target」（即 LeetCode 39/40 类变体）时，引入记忆化能显著提升性能。但许多开发者会陷入一个隐蔽却致命的问题：对嵌套列表仅做浅拷贝，导致 memo 中缓存的 List> 被后续递归调用意外修改
——这正是原代码输出异常的根本原因。
观察原始代码的关键缺陷：
memo.put(target, new ArrayList<>(temp)); // ❌ 浅拷贝：外层 List 被复制，但每个 inner List 仍是原引用！
当 temp 中的某个 List
✅ 正确做法是深度克隆整个嵌套结构：不仅新建外层 List，还要为每个内层 List
立即学习“Java免费学习笔记（深入）”；
// ✅ 深拷贝：为每个子列表创建新 ArrayList 实例
List<List<Integer>> deepCopy = temp.stream()
.map(ArrayList::new) // 对每个 List<Integer> 构造新 ArrayList
.collect(Collectors.toList());
memo.put(target, deepCopy);同时，读取 memo 时也必须深拷贝，否则返回的引用仍可能被调用方修改并反向污染缓存：
if (memo.containsKey(target)) {
return new ArrayList<>( // 复制外层
memo.get(target).stream()
.map(ArrayList::new) // 每个内层也复制
.collect(Collectors.toList())
);
}完整修正版（含主函数验证）：
import java.util.*;
import java.util.stream.Collectors;
public class CombinationSumMemo {
static private List<List<Integer>> allCombinationDP(
int[] candidates, int target, Map<Integer, List<List<Integer>>> memo) {
if (target < 0) return null;
if (target == 0) {
List<List<Integer>> base = new ArrayList<>();
base.add(new ArrayList<>());
return base;
}
if (memo.containsKey(target)) {
// ✅ 读取时深拷贝：防止返回引用污染 memo
return new ArrayList<>(
memo.get(target).stream()
.map(ArrayList::new)
.collect(Collectors.toList())
);
}
List<List<Integer>> temp = new ArrayList<>();
for (int candidate : candidates) {
int remainder = target - candidate;
List<List<Integer>> subResults = allCombinationDP(candidates, remainder, memo);
if (subResults != null) {
for (List<Integer> combo : new ArrayList<>(subResults)) { // 遍历时防 ConcurrentModification
combo.add(candidate); // ✅ 修改的是副本，不影响 memo 中缓存
temp.add(combo);
}
}
}
// ✅ 存入前深拷贝
List<List<Integer>> deepCopy = temp.stream()
.map(ArrayList::new)
.collect(Collectors.toList());
memo.put(target, deepCopy);
return temp; // 返回当前计算结果（非 memo 引用）
}
public static void main(String[] args) {
int[] candidates = {1, 2, 3};
int target = 3;
Map<Integer, List<List<Integer>>> memo = new HashMap<>();
List<List<Integer>> result = allCombinationDP(candidates, target, memo);
System.out.println("Result: " + result);
// 输出: [[1, 1, 1], [2, 1], [1, 2], [3]] —— 正确且无重复污染
}
}⚠️ 关键注意事项：
- 永远不要直接缓存或返回可变集合的原始引用，尤其在递归+记忆化场景；
- 使用 stream().map(ArrayList::new).collect(...) 是 Java 8+ 中简洁可靠的深拷贝方式；
- 遍历 subResults 时用 new ArrayList(subResults) 包裹，避免 ConcurrentModificationException；
- 若需更高性能或处理超大嵌套结构，可考虑自定义深拷贝工具类或使用不可变集合（如 Guava 的 ImmutableList）。
通过严格区分「计算时的临时集合」与「memo 中的只读快照」，你就能写出既高效又健壮的记忆化递归代码。
