Java组合总和递归记忆化存储值异常问题求助

我正在练习Java递归函数，递归功能正常，但实现组合总和问题的记忆化时，存入memo的值会被后续修改，导致memo最终值错误。多次调试无果，求指导。

原代码 #

static private List<List<Integer>> allCombinationDP(int[] candidates, int target, Map<Integer,List<List<Integer>>> memo ){
    List<List<Integer>> temp = new ArrayList<>();
    // Map<Integer,List<List<Integer>>> memo = new HashMap<>();
    
    if (target <0) return null;
    if (target ==0) {
      List<List<Integer>> ansSet = new ArrayList<>();
      ansSet.add(new ArrayList<>());
      return ansSet;
    }

    for (int i=0, n=candidates.length; i<n;i++){
      int remainder = target - candidates[i];
      List<List<Integer>> result = allCombinationDP(candidates, remainder,memo);
      if (result != null){
        for (int j =0, m=result.size(); j<m;j++) {
          result.get(j).add( candidates[i] );
        }
        temp.addAll(new ArrayList<>(result));
      }
    }
    memo.put(target, new ArrayList<>(temp));
    System.out.println(memo.toString());
    return temp;
  }

public static void main(String[] args) {
    int[] candidates = {1,2,3};
    int target = 3;
    
    System.out.println(allCombinationDP(candidates, target, new HashMap<>()) );
}

当前输出 #

{1=[ [1] ] }
{1=[ [1, 1] ], 2=[ [1, 1], [2] ] }
{1=[ [1] ], 2=[ [1, 1, 1], [2, 1] ] }
{1=[ [1, 2] ],  2=[ [1, 1, 1], [2, 1] ],  3=[ [1, 1, 1], [2, 1], [1, 2], [3] ] }

[  [1, 1, 1], [2, 1], [1, 2], [3] ]

期望输出 #

{1=[ [1] ] }
{1=[ [1] ], 2=[ [1, 1], [2] ] }
{1=[ [1] ], 2=[ [1, 1], [2] ] }
{1=[ [1] ], 2=[ [1, 1], [2] ], 3=[ [1, 1, 1], [2, 1], [1, 2], [3] ] }

[  [1, 1, 1], [2, 1], [1, 2], [3] ]

问题根源 #

你直接修改了递归返回的result中的列表元素——这些列表是引用类型，当你在上层递归调用result.get(j).add(candidates[i])时，会直接修改memo中已存储的列表内容（因为memo里存的是这些列表的引用）。此外，原代码完全没用到memo的缓存功能，每次都重复计算，违背了记忆化递归的初衷。

修复方案 #

修改核心是切断引用关联，所有对递归返回列表的操作都基于副本，同时补上memo的缓存检查逻辑：

修改后的代码 #

static private List<List<Integer>> allCombinationDP(int[] candidates, int target, Map<Integer,List<List<Integer>>> memo ){
    // 优先检查memo，避免重复计算
    if (memo.containsKey(target)) {
        // 返回副本，防止外部修改memo内的原始数据
        List<List<Integer>> copy = new ArrayList<>();
        for (List<Integer> list : memo.get(target)) {
            copy.add(new ArrayList<>(list));
        }
        return copy;
    }

    List<List<Integer>> temp = new ArrayList<>();
    
    if (target < 0) return null;
    if (target == 0) {
        List<List<Integer>> ansSet = new ArrayList<>();
        ansSet.add(new ArrayList<>());
        return ansSet;
    }

    for (int i = 0, n = candidates.length; i < n; i++){
        int remainder = target - candidates[i];
        List<List<Integer>> result = allCombinationDP(candidates, remainder, memo);
        if (result != null){
            // 为每个子列表创建副本，再添加当前候选数，不修改原列表
            for (List<Integer> subList : result) {
                List<Integer> newSubList = new ArrayList<>(subList);
                newSubList.add(candidates[i]);
                temp.add(newSubList);
            }
        }
    }
    // 存入memo时，存储所有子列表的副本，彻底切断引用
    List<List<Integer>> memoValue = new ArrayList<>();
    for (List<Integer> list : temp) {
        memoValue.add(new ArrayList<>(list));
    }
    memo.put(target, memoValue);
    System.out.println(memo.toString());
    return temp;
}

public static void main(String[] args) {
    int[] candidates = {1,2,3};
    int target = 3;
    
    System.out.println(allCombinationDP(candidates, target, new HashMap<>()) );
}

关键修改说明 #

• 新增memo缓存检查：每次递归先判断目标值是否已缓存，避免重复计算，这是记忆化递归的核心
• 操作副本而非原列表：处理递归返回的result时，为每个子列表创建新副本再添加元素，不会污染memo中已存储的结果
• 存入memo的是独立副本：将temp中的所有列表复制后再存入memo，确保后续递归操作不会修改已缓存的内容

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