数组全排列生成函数工作原理及回溯执行逻辑疑问解答

问题描述 #

我尝试实现数组的全排列但没成功，比如数组[1,2,3]应该返回[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。后来参考了别人的回溯法实现代码，但搞不懂它的工作机制，尤其疑惑两个点：

• 调用dfs()之后为什么还能执行到path.pop()语句？
• 循环是怎么终止的？

参考代码 #

const permute = (nums) => {
    // Backtracking
    const used = new Set(); // 记录已使用的元素
    const path = []; // 当前正在构建的排列路径
    const res = []; // 存储最终所有排列结果
    
    const dfs = () => {
        // 递归终止条件：当前路径长度等于原数组长度，说明得到一个完整排列
        if(path.length === nums.length) {
            res.push([...path]); // 用扩展运算符克隆数组，避免后续修改影响已存入的结果
            return; // 加上return可提前终止当前dfs的循环，提升效率
        }
        
        // 每次递归都遍历原数组所有元素
        for(let i = 0; i < nums.length; i++) {
            // 跳过已使用过的元素
            if(used.has(nums[i])) continue;
            
            // 将当前元素加入路径，并标记为已使用
            path.push(nums[i]);
            used.add(nums[i]);
            
            // 递归进入下一层，继续构建路径
            dfs();
            
            // 回溯：移除当前元素，取消标记，为尝试其他分支做准备
            path.pop();
            used.delete(nums[i])
        }
    }
    
    // 启动递归
    dfs();
    
    return res;
}

核心疑问解答 #

1. 为什么调用dfs()后还能执行path.pop()？ #

这是递归的回溯特性决定的：
当你在当前dfs()函数里调用dfs()时，当前函数的执行会暂停在调用语句的位置，优先执行被调用的dfs()函数——直到这个被调用的dfs()完全执行完（包括它内部的所有循环、递归调用、以及末尾的语句），才会回到当前函数，继续执行dfs()后面的path.pop()和used.delete()。

拿[1,2,3]的执行流程举例：

• 第一层dfs()：path为空，i=0，把1加入path和used，调用第二层dfs()。
• 第二层dfs()：path是[1]，i=1，把2加入path和used，调用第三层dfs()。
• 第三层dfs()：path是[1,2]，i=2，把3加入path，此时path长度等于nums长度，把[1,2,3]加入res。接着第三层的for循环走到i=3（超出nums.length，循环结束），第三层dfs()执行完毕，回到第二层dfs()中调用dfs()的位置，此时开始执行path.pop()（删掉3）、used.delete(3)。
• 之后第二层的for循环继续i=2，把3加入path，调用第三层dfs()得到[1,3,2]，接着第三层执行完回到第二层，再次执行回溯操作...

简单说：走完一条完整的排列路径（得到一个结果），就需要“回退”一步，把最后加的元素撤掉，才能去尝试另一条不同的分支路径。

2. 循环是怎么终止的？ #

循环的终止分两层逻辑：

• 单个dfs()内的for循环：当循环变量i递增到等于nums.length时，循环自然终止。
• 整个递归过程的终止：当第一层dfs()的for循环从i=0到i=nums.length-1全部执行完毕，所有可能的排列路径都被尝试过，整个递归就会终止。

另外，当path.length === nums.length时，原代码没写return，但此时当前dfs()的for循环后续迭代都会因为元素已被used标记而触发continue，直到i走到nums.length，循环结束，当前dfs()执行完毕回到上一层。如果在这个条件里加上return，可以提前终止当前dfs()的循环，减少不必要的判断。

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