JavaScript递归子集函数异常：a、b值重复，数组引用问题求助

问题根源 #

你遇到的问题本质是数组的引用传递特性：JavaScript里数组是引用类型，你传给递归函数的arr始终是同一个内存地址的引用。第一次递归调用subset(n+1, arr)得到的a里，保存的都是这个arr的引用；之后你给arrpush元素时，a里的所有数组也会跟着改变——因为它们指向同一个数组对象。到最后a和b的结果自然会完全相同，所有递归分支都共享了同一个被修改后的数组。

无额外空间的解决方案：回溯法 #

不用每次递归都复制数组，而是用回溯的思路：修改数组后完成递归，再把修改的部分还原，复用同一个数组对象，只在必要的时候（保存最终结果）做一次复制。

修改后的代码如下：

let subset = function(n, arr) {
    // 递归终止：遍历完所有元素，保存当前数组的副本（必须复制，否则后续回溯会修改这个结果）
    if (n === array.length) {
        return [ [...arr] ];
    }

    // 分支1：不选当前元素，直接递归下一个
    let a = subset(n + 1, arr);

    // 分支2：选当前元素，先push再递归
    arr.push(array[n]);
    let b = subset(n + 1, arr);
    // 回溯：把刚push的元素弹出，恢复数组到之前的状态
    arr.pop();

    return a.concat(b);
}

let array = [1, 2, 3];
console.log(subset(0, []));

关键细节说明 #

1. 回溯的作用：arr.pop()是核心，它把push的元素移除，让数组回到调用分支2之前的状态，这样后续的递归分支不会受到当前分支修改的影响，实现了用同一个数组模拟不同分支的状态。
2. 终止时的复制：递归到最后必须返回[...arr]而不是[arr]，因为如果直接返回原数组引用，后续的回溯操作会把这个数组清空，最终所有子集结果都会变成空数组。这一步的复制是必要的，但只在叶子节点执行，空间开销远小于递归过程中每次复制数组。

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