JavaScript回溯法递归求数组子集输出全空数组问题排查

问题根因 #

JavaScript中数组是引用类型，你代码里ans.push(sub)时实际存入ans的是sub数组的内存引用，而非当前sub的快照。后续你调用sub.pop()修改数组内容时，所有已经存入ans的引用指向的数组内容也会同步被修改，递归执行结束后sub最终会被清空为[]，所以ans里的8个引用最终都指向同一个空数组。

修复方案 #

只需要修改递归终止条件里的入队逻辑，存入ans时创建当前sub数组的浅拷贝即可：

// 修改printAllSubset的base条件部分
if(idx == nums.length){
    ans.push([...sub]); // 这里创建浅拷贝，存入当前sub的快照
    return ans;
}

还有两处不影响核心逻辑但需要清理的小问题：

• 你代码里if(idx==nums.length){. 多了一个多余的英文句号，会触发语法错误，直接删除即可
• 调用solveIt(A,B,C)时传入的B、C变量未定义，因为solveIt里没有用到这几个参数所以不影响运行，建议清理无用参数避免语法警告

完整可运行代码 #

// 主函数
function solveIt(A){
    let ans = [];
    let sub = [];
    printAllSubset(A, 0, sub, ans);
    return ans;
}

// 递归回溯函数
function printAllSubset(nums, idx, sub, ans){
    if(idx == nums.length){
        ans.push([...sub]);
        return ans;
    }
    // 包含当前索引元素
    sub.push(nums[idx]);
    printAllSubset(nums, idx + 1, sub, ans);
    // 排除当前索引元素
    sub.pop();
    printAllSubset(nums, idx + 1, sub, ans);
}

const A = [1,2,3];
const res = solveIt(A);
console.log(res);
// 输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] 符合预期

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