Java递归求目标和最短组合时sol列表未正确更新的疑问

错误原因 #

• Java是值传递，你向recursion方法传递sol参数时，实际传递的是main方法中sol对象引用的副本。你在方法内执行sol = lst操作，只是修改了这个局部引用副本的指向，让它指向了lst对应的列表地址，完全不会影响main方法中原来的sol对象的内容。
• 而minLen数组能生效的原因是你没有修改数组引用本身，只是修改了数组内部存储的元素值，操作的是同一个堆上的数组对象，所以改动能全局生效。

修复方案 #

不需要修改递归函数返回值，只要把「给sol重新赋值」的逻辑改成「修改sol对象内部的内容」即可：

1. 当找到和为tgt的有效组合时，只有当前路径长度小于当前的最小长度时，才更新minLen和sol，避免无效更新
2. 更新sol时不要直接赋值，先清空sol原有内容，再把当前路径的所有元素添加到sol中
3. 补充recursion方法的static修饰，否则静态main方法无法直接调用非静态方法

修正后的完整代码 #

import java.util.*;

public class MyClass {
    public static void main(String args[]) {
        int[] arr = new int[]{2,3,4,5};
        int[] min = new int[]{Integer.MAX_VALUE};
        int tgt = 7;
        List<Integer> lst = new ArrayList<>();
        List<Integer> sol = new ArrayList<>();
        
        recursion(arr, tgt, lst, min, sol);
        
        for (int i = 0; i < sol.size(); i++) {
            System.out.println(sol.get(i));
        }
    }
    
    // 补充static修饰
    public static void recursion(int[] nums, int tgt, List<Integer> lst, int[] minLen, List<Integer> sol) {
        if (tgt < 0) {
            return;
        }
        if (tgt == 0) {
            // 只有当前路径长度更小才更新
            if (lst.size() < minLen[0]) {
                minLen[0] = lst.size();
                // 直接修改sol对象内部内容，不改变引用指向
                sol.clear();
                sol.addAll(lst);
            }
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            List<Integer> cpy = new ArrayList<>(lst);
            cpy.add(nums[i]);
            recursion(nums, tgt - nums[i], cpy, minLen, sol);
        }
    }
}

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