LeetCode #46 Permutations：回溯过程中弹出元素的逻辑疑问

问题背景 #

给定由不同整数组成的数组nums，返回其所有可能的排列，返回顺序不限。示例输入nums = [1,2,3]，输出为[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

JavaScript解法代码 #

let permute = function(nums) {
    if(nums.length === 0) return [nums];
    let res = [], len = nums.length,used = new Array(len).fill(false);

    let backtrack = function(currPermutation){
        if(currPermutation.length === nums.length){
            res.push([...currPermutation]);
            return;
        }

        for(let i = 0; i < len; ++i){
            if(used[i]) continue;

            currPermutation.push(nums[i]);
            console.log("curr perm = ",currPermutation);
            used[i] = true;
            backtrack(currPermutation);
            currPermutation.pop();
            used[i] = false;
        }
    }

    backtrack([]);
    return res;
};

permute([1,2,3]);

控制台输出 #

curr perm =  [ 1 ]
curr perm =  [ 1, 2 ]
curr perm =  [ 1, 2, 3 ]
curr perm =  [ 1, 3 ]
curr perm =  [ 1, 3, 2 ]
curr perm =  [ 2 ]
curr perm =  [ 2, 1 ]
curr perm =  [ 2, 1, 3 ]
curr perm =  [ 2, 3 ]
curr perm =  [ 2, 3, 1 ]
curr perm =  [ 3 ]
curr perm =  [ 3, 1 ]
curr perm =  [ 3, 1, 2 ]
curr perm =  [ 3, 2 ]
curr perm =  [ 3, 2, 1 ]

疑问点 #

当curr perm = [1,2,3]时，为何代码会弹出数字2而非3？同理，当curr perm = [2,1,3]时为何弹出1而非3，curr perm = [3,1,2]时为何弹出1而非2？

解答 #

你误解了弹出操作和console.log输出的对应关系——console.log打印的是push元素后的数组状态，而弹出操作是在当前回溯函数返回后执行的，两者不是直接绑定在同一次输出上。

拿curr perm = [1,2,3]的情况拆解执行流程：

1. 当数组变成[1,2,3]时，触发终止条件，把这个排列存入结果集，当前的回溯函数直接返回，回到上一层调用（也就是生成[1,2]的那次回溯循环）。
2. 回到上一层后，首先执行currPermutation.pop()，弹出的是最后加入的3，数组变回[1,2]，同时标记used[2] = false。
3. 这一层的循环（i=2）结束，i递增到3后退出循环，回到生成[1,2]的那一层回溯函数。
4. 此时该层回溯函数执行currPermutation.pop()，弹出的是2，数组变回[1]，标记used[1] = false。
5. 接着该层循环i递增到2，此时used[2]是false，push3后数组变成[1,3]，这就是下一个console.log输出的内容。

同理：

• 对于curr perm = [2,1,3]：它对应的第一步弹出是3，数组变回[2,1]；回到上一层后再弹出1，数组变回[2]，之后push3得到[2,3]。
• 对于curr perm = [3,1,2]：它对应的第一步弹出是2，数组变回[3,1]；回到上一层后再弹出1，数组变回[3]，之后push2得到[3,2]。

简单来说：每个console.log的数组是一次push后的状态，而弹出操作是先弹掉该数组最后加入的元素，回到上一层后再弹上一个元素，才会生成下一个控制台输出的数组。

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