求解数组幂集的Java回溯代码返回错误结果如何修复

问题表现 #

给定元素均唯一的整数数组nums，需要返回数组的所有可能子集（幂集）。以输入[1,2]为例：

• 预期正确结果（子集顺序不影响正确性）：[[],[1],[2],[1,2]]
• 原代码实际错误输出：[[],[2],[2,1],[2,1,2]]，存在元素重复、状态错乱问题。

错误根因 #

原代码的回溯逻辑缺失状态回退步骤：
当执行「选择当前元素加入子集」的分支时，向output列表添加元素后，递归完成没有将该元素从列表中移除，导致output的状态会被带到其他递归分支，造成跨分支的状态污染，最终出现重复元素、结果不符合预期的问题。

修复方案 #

在「选择当前元素」的递归调用结束后，移除output列表末尾刚加入的元素，将列表状态回退到选择元素之前的状态，即可避免不同递归分支的状态互相干扰。
修复后的完整代码如下：

class Solution {
    
    private List<List<Integer>> ans= new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        solve(nums, 0, new ArrayList<>());
        return ans;
    }
    
    
    public void solve(int[] nums, int i, List<Integer> output)
    {
        if(i == nums.length)
        {
            ans.add(new ArrayList(output));
            return;
        }
        
        
        // 分支1：不选择当前位置元素
        solve(nums, i+1, output);
        
        
        // 分支2：选择当前位置元素
        output.add(nums[i]);
        solve(nums, i+1, output);
        // 回溯：撤销选择，回退状态
        output.remove(output.size() - 1);
            
    }
}

说明：上述代码运行输出为[[],[2],[1],[1,2]]，和示例给出的结果仅子集顺序不同，内容完全符合幂集要求，所有题目判题规则均会接受该结果。幂集本身是集合的集合，不要求内部子集的排列顺序，如果需要完全匹配示例的顺序，只需要把「选择当前元素」的分支调整到「不选择当前元素」分支之前即可，核心回溯逻辑不变。

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