回溯逻辑理解困惑：子集生成代码中元素移除的疑问

你用回溯法实现了唯一元素数组的子集生成，代码能正确运行，但对tempList=[1,2,3]时tempList.remove(tempList.size()-1)的执行逻辑有疑问，下面直白拆解这部分的调用过程：

你的代码 #

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> solution= new ArrayList<>();
        backtrack(solution,new ArrayList<>(), nums,0);
        return solution;
    }

    private void backtrack(List<List<Integer>> sol, List<Integer>tempList, int[] nums, int start){
        sol.add(new ArrayList<>(tempList));
        for(int i=start;i<nums.length;i++){
            if(!tempList.contains(nums[i])){
                tempList.add(nums[i]);
                backtrack(sol,tempList,nums,i);   
                tempList.remove(tempList.size()-1);
            }
        }
    }
}

核心逻辑拆解 #

你疑惑的remove操作，并不是在tempList=[1,2,3]的那层递归调用里执行的，而是在它的上一层调用中执行的，具体流程如下：

1. 当程序执行到tempList=[1,2]、start=1、i=2时，nums[i]=3不在tempList里，于是执行tempList.add(3)，此时tempList变成[1,2,3]。
2. 接着调用backtrack(sol, [1,2,3], nums, 2)——这是新的一层递归：
   • 首先把[1,2,3]加入结果集；
   • 进入for循环，i从2开始，nums[2]=3已经在tempList里，if条件不满足，循环直接结束，这层递归调用直接返回。
3. 回到上一层（也就是调用backtrack(sol, [1,2,3], nums, 2)的那层），此时代码执行到backtrack(...)之后的tempList.remove(tempList.size()-1)，把3移除，tempList变回[1,2]。
4. 这层的for循环结束后，继续回到更上一层（tempList=[1]、start=0、i=1的那层），执行remove操作移除2，tempList变回[1]，后续继续处理i=2的情况（生成[1,3]）。

简单来说：remove是当前层添加元素后，等待下层递归完全处理完所有分支，再执行的「回溯清理」操作，和下层递归里的if条件没有关系——下层递归的条件只决定它会不会继续深入，不影响当前层在它返回后执行清理。

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