Leetcode 78子集问题：回溯中为何需重复复制列表？

问题背景 #

复习Leetcode第78题「Subsets（子集）」时发现，回溯代码的base case中必须添加perm的副本才能得到正确结果；但「Permutations（全排列）」的回溯代码里，直接添加perm就行。想搞清楚这种差异的根源。

子集代码的复制必要性分析 #

先看子集的回溯实现：

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(new ArrayList<Integer>(), 0, nums);
        return list;
    }
    
    private void dfs(List<Integer> perm, int choice, int[] choices){
        if(choice >= choices.length){
            list.add(new ArrayList<>(perm));
            return;
        }
        
        List<Integer> temp = new ArrayList<>(perm);
        temp.add(choices[choice]);
        dfs(temp,choice+1,choices);
        temp.remove(temp.size()-1);
        dfs(temp,choice+1,choices);
    }
}

这里的关键矛盾点是：同一个temp列表被修改后重复使用了。

当执行temp.add(choices[choice])后进入递归，递归返回后，我们会执行temp.remove(...)把刚才加的元素删掉，让temp回到初始状态，再进入下一个递归分支。如果base case里直接把perm（也就是当前的temp）加入结果集，后续的remove操作会直接修改结果集里的列表——因为Java里列表是引用类型，结果集存的是指向列表的引用，不是元素的拷贝。

举个例子：假设某次递归到base case，把perm加入了list，回到上一层后执行temp.remove，这个操作会同时改动list里已经存着的那个列表，最终导致结果集里的元素被篡改，出现错误。所以必须在base case时创建一个新的ArrayList副本，把当前perm的状态固定下来，避免后续修改影响结果。

全排列代码无需复制的原因 #

再看全排列的回溯实现：

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> dt = new ArrayList<>();
        for(int n:nums) dt.add(n);
        dfs(new ArrayList<>(), dt);
        return list;
    }
    
    private void dfs(List<Integer> perm, List<Integer> dt){
        if(dt.size() == 0){
            list.add(perm);
            return;
        }
        
        for(Integer n:dt){
            List<Integer> tempP = new ArrayList<>(perm);
            List<Integer> tempD = new ArrayList<>(dt);
            tempP.add(n);
            tempD.remove(n);
            dfs(tempP,tempD);
        }
    }
}

这里的核心逻辑是：每个递归分支都用的是全新的列表副本。

在for循环的每一轮里，我们都会创建tempP（当前perm的副本）和tempD（当前dt的副本），修改这两个副本后再传入递归。也就是说，每个递归调用拿到的perm都是独立的新列表，没有其他代码会持有它的引用并进行修改。当到达base case时，这个perm（也就是tempP）的状态已经固定，后续的循环操作不会对它有任何影响，所以直接把它加入结果集就可以，完全不需要再复制。

差异本质总结 #

• 子集代码中存在同一列表被多次修改复用的场景，base case不复制的话，后续操作会篡改结果集里的元素；
• 全排列代码中每个递归分支都使用独立的列表副本，传入递归的列表不会被后续代码修改，因此base case直接添加即可。

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