数组/字符串幂集求解：回溯remove操作作用与实现差异疑问

问题背景 #

给定元素均唯一的整数数组nums，需返回其所有可能子集（即幂集）。例如输入[1,2]时，预期正确输出为[[],[1],[2],[1,2]]。
目前已写出可正常运行的数组幂集求解代码，但存在两点疑问：

• 数组求解代码中output.remove(output.size()-1);语句的作用是什么？
• 求解字符串"ABC"幂集时未编写上述回溯移除逻辑，仍可正确输出所有幂集结果，两种实现存在差异的原因是什么？
  其中字符串幂集的求解代码如下：

String s = "ABC";
ps(s, 0, "");
public static void ps(String str, int i, String ans) {
    if (i == str.length()) {
        System.out.println(" Print " + ans);
        return;
    }
    ps(str, i + 1, ans + str.charAt(i));
    ps(str, i + 1, ans);
}

问题解答 #

1. output.remove(output.size()-1)的作用 #

这行是回溯算法的状态撤销核心步骤。
编写数组幂集代码时，一般会复用一个类似ArrayList的可变集合，在递归过程中持续存储当前正在拼接的子集：

• 当你将当前元素加入集合、递归走完「选择当前元素」的所有分支后，必须把刚加入的这个元素从集合末尾移除，将集合恢复到加入元素之前的状态，才能正确进入「不选择当前元素」的分支继续递归。
  以输入[1,2]为例：先把1加入集合，再把2加入集合，拿到有效子集[1,2]；这时候如果不删除末尾的2，直接走不选2的分支，集合里还留存着2，根本无法得到[1]这个子集。等选择1的全部分支跑完，还需要删除末尾的1，回到集合为空的初始状态，才能正确走不选1的分支，拿到[2]和[]两个结果。
  如果没有这行撤销操作，同一个可变集合的状态会在不同递归分支之间互相污染，最终输出的结果会完全不符合预期。

2. 字符串幂集无需手动撤销的原因 #

两种实现的核心差异是递归过程中传递状态的方式完全不同：数组实现传递的是可变对象的引用，字符串实现传递的是不可变对象的全新副本，因此不需要手动做撤销操作。
字符串版本的递归参数ans是Java中的String类型，而String天生是不可变的：

• 当你写ans + str.charAt(i)时，并没有修改当前递归层的ans对象本身，而是直接生成了一个拼接了当前字符的全新字符串，传给下一层递归使用。
• 等「选择当前字符」的递归分支执行完回到当前层时，当前层持有的ans还是未拼接当前字符的原始状态，可以直接调用「不选择当前字符」的递归逻辑，完全不需要手动删除字符做状态回退。
  打个直白的比方：数组幂集的写法相当于多个人共用一块白板写当前子集，写完一个分支必须擦掉刚写的内容，才能写下一个分支的内容；字符串幂集的写法相当于每进入一个新分支就发一张全新的草稿纸书写，当前层原来的草稿纸内容完全没有改动，自然不需要做擦除操作。

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