本文详解如何在 Java 中对“组合总和”递归算法进行安全的记忆化（memoization），重点解决因浅拷贝导致的 memo 值被意外修改、结果错乱的核心问题，并提供深拷贝实现方案与完整可运行代码。
本文详解如何在 java 中对“组合总和”递归算法进行**安全的记忆化（memoization）**，重点解决因浅拷贝导致的 memo 值被意外修改、结果错乱的核心问题，并提供深拷贝实现方案与完整可运行代码。
在解决「所有组合总和等于目标值」这类经典回溯/递归问题时，引入记忆化可显著提升性能——但若处理不当，反而会引发隐蔽而严重的逻辑错误。你遇到的问题正是典型：memo.put(target, new ArrayList(temp)) 仅执行了浅拷贝——外层 List 被复制了，但内部每个 List
✅ 正确做法：全程深拷贝
每次存入 memo 前，必须对 List> 进行深度克隆：不仅新建外层列表，还要为每个子列表创建独立副本：
// ✅ 深拷贝：为每个 inner list 创建新 ArrayList
List<list>> deepCopy = temp.stream()
.map(ArrayList::new) // 对每个 List<integer> 构造新实例
.collect(Collectors.toList());
memo.put(target, deepCopy);</integer></list>
同样，从 memo 中读取时也需深拷贝，避免返回引用后被上游修改：
if (memo.containsKey(target)) {
return new ArrayList(memo.get(target)
.stream()
.map(ArrayList::new)
.collect(Collectors.toList()));
}
? 错误示例解析（原代码问题）
原始代码中：
memo.put(target, new ArrayList(temp)); // ❌ 浅拷贝！
假设 temp = [[1]]，new ArrayList(temp) 生成新列表 [[1]]，但其唯一元素仍是对原 ArrayList
✅ 完整修正版代码（含注释）
import java.util.*;
import java.util.stream.Collectors;
public class CombinationSumMemo {
static private List<list>> allCombinationDP(
int[] candidates, int target, Map<integer list>>> memo) {
if (target > base = new ArrayList();
base.add(new ArrayList()); // 空组合
return base;
}
if (memo.containsKey(target)) {
// ✅ 读取时也深拷贝，防止外部修改影响缓存
return memo.get(target).stream()
.map(ArrayList::new)
.collect(Collectors.toList());
}
List<list>> temp = new ArrayList();
for (int candidate : candidates) {
int remainder = target - candidate;
List<list>> subResults = allCombinationDP(candidates, remainder, memo);
if (subResults != null) {
for (List<integer> combo : subResults) {
List<integer> newCombo = new ArrayList(combo); // ✅ 新建子列表
newCombo.add(candidate);
temp.add(newCombo);
}
}
}
// ✅ 存入 memo 前深拷贝（等价于 map(ArrayList::new)）
List<list>> deepCopied = new ArrayList();
for (List<integer> combo : temp) {
deepCopied.add(new ArrayList(combo));
}
memo.put(target, deepCopied);
return temp; // 返回当前计算结果（非引用缓存值）
}
public static void main(String[] args) {
int[] candidates = {1, 2, 3};
int target = 3;
Map<integer list>>> memo = new HashMap();
List<list>> result = allCombinationDP(candidates, target, memo);
System.out.println(result);
// 输出: [[1, 1, 1], [1, 2], [2, 1], [3]]
}
}</list></integer></integer></list></integer></integer></list></list></integer></list>
⚠️ 关键注意事项
- 不要复用子列表：永远用 new ArrayList(original) 创建新实例，而非 original.clone()（未重写 clone() 的 ArrayList 可能不安全）。
- memo 的 key 设计合理：当前以 target 为 key 是可行的，但注意该解法允许重复使用同一数字且顺序不同视为不同组合（如 [1,2] 和 [2,1]）。若要求去重或限制顺序，需额外状态（如 start index），此时 memo key 应扩展为复合键（如 target + "_" + startIndex）。
- 空间权衡：深拷贝带来额外内存开销，但在组合类问题中，结果集本身已具规模，此开销通常可接受；若极端追求性能，可考虑不可变数据结构（如 ImmutableList），但需引入 Guava 等依赖。
通过严格遵循“存前深拷、取后深拷”原则，你的记忆化递归将既高效又健壮——不再被幽灵般的引用修改所困扰。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
