Java 中组合总和问题的正确记忆化实现：避免浅拷贝导致的引用污染-java教程-PHP中文网

Java 中组合总和问题的正确记忆化实现：避免浅拷贝导致的引用污染

本文详解如何在 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（如 [1]）被后续 result.get(j).add(candidates[i]) 修改为 [1, 1] 时，已存入 memo 的同一对象也被改写，造成缓存污染。这就是为何 target=1 对应的 memo 值从 [ [1] ] 变成了 [ [1, 1] ] 或 [ [1, 2] ]。

✅ 正确做法是深度克隆整个嵌套结构：不仅新建外层 List，还要为每个内层 List 创建独立副本：

// ✅ 深拷贝：为每个子列表创建新 ArrayList 实例
List<list>> deepCopy = temp.stream()
    .map(ArrayList::new)        // 对每个 List<integer> 构造新 ArrayList
    .collect(Collectors.toList());
memo.put(target, deepCopy);</integer></list>

同时，读取 memo 时也必须深拷贝，否则返回的引用仍可能被调用方修改并反向污染缓存：

Java调试

通过 JDWP 实现 Java 远程调试：连接远程 JVM、设置断点、单步执行代码、查看变量值、获取调用栈。适用于需要调试远程 Java 应用、排查运行时状态、追踪代码执行流程的场景。术语注解 JDWP：Java Debug Wire Protocol，Java 调试有线协议（Java 远程调试底层通信协议） remote JVM：远程 Java 虚拟机 step through code：代码单步调试（步入 / 步过 / 步出调试） inspect variables：变量查看 / 变量检视 stac

下载

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>> allCombinationDP(
            int[] candidates, int target, Map<integer list>>> memo) {
        if (target > 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>> 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 : new ArrayList(subResults)) { // 遍历时防 ConcurrentModification
                    combo.add(candidate); // ✅ 修改的是副本，不影响 memo 中缓存
                    temp.add(combo);
                }
            }
        }

        // ✅ 存入前深拷贝
        List<list>> 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>>> memo = new HashMap();
        List<list>> result = allCombinationDP(candidates, target, memo);
        System.out.println("Result: " + result);
        // 输出: [[1, 1, 1], [2, 1], [1, 2], [3]] —— 正确且无重复污染
    }
}</list></integer></list></integer></list></list></integer></list>

⚠️ 关键注意事项：

永远不要直接缓存或返回可变集合的原始引用，尤其在递归+记忆化场景；
使用 stream().map(ArrayList::new).collect(...) 是 Java 8+ 中简洁可靠的深拷贝方式；
遍历 subResults 时用 new ArrayList(subResults) 包裹，避免 ConcurrentModificationException；
若需更高性能或处理超大嵌套结构，可考虑自定义深拷贝工具类或使用不可变集合（如 Guava 的 ImmutableList）。

通过严格区分「计算时的临时集合」与「memo 中的只读快照」，你就能写出既高效又健壮的记忆化递归代码。