在达到基本情况后进行排列时递归如何工作

Question

当达到基本情况时，对于下一个组合调用，我们重新交换它的考虑方式，以考虑未访问或考虑的情况

例如

 function dfs(i, nums, slate) {
    if (i === nums.length) {
        result.push(slate.slice());
        return; // Terminate the current branch of recursion
    }

    for (let j = i; j < nums.length; j++) {
        [nums[i], nums[j]] = [nums[j], nums[i]]; // Swap elements
        dfs(i + 1, nums, slate.concat(nums[i])); // Recur with the next index
        [nums[i], nums[j]] = [nums[j], nums[i]]; // Backtrack: Restore original state
    }
}

在交换此代码如何获取下一个值或未访问的值或未考虑的值（因为我们不返回任何内容）后，我们将恢复到原始值。任何人都可以帮助我理解

就像我想了解堆栈调用的展开以及如何考虑下一个情况。达到基本情况之后以及它是如何工作的。谢谢

Answer 1

该算法的背景如下：

通过重复从输入列表中选择任何可用值以成为我们正在构建的排列中的下一个值来形成排列。在此过程中，可用值的数量会减少，直到没有更多值，同时选定值的数量会增加，直到我们获得完整的排列。

为了获得其他排列，我们需要在每个索引处进行所有可能的选择，因此通过回溯，我们可以撤消最近做出的选择，并在可能的情况下选择另一个值。当在该阶段尝试了所有可能性后，我们再次回溯以处理那里的替代方案，...等等。

一个关键的见解是，该算法为所选部分保留输入数组的左侧，并为其余选择保留数组的右侧以存储仍然“可用”的值。这两个子数组之间的间隔位于索引 i 处。左侧分区具有

size

i，右侧分区从该索引开始。假设我们已经选择了一些值，并且位于索引

i

。这里的目标是从正确的分区中选择一个值并将其放置在索引

i

处（它甚至可以是该索引处已经存在的值，因为该值也属于正确的分区）。一旦我们选择了它，我们就可以将该索引声明为左分区的一部分。我们通过使用

i + 1

进行递归调用来完成此操作。交换机制（当

j > i

时）用于实现两件事：

将所选值从索引

j
1. 移到索引

   i

   ，这样现在它就被

   选中

   ，并且一旦 i 递增，它将成为左侧分区的一部分。将索引
i
2. 处未选定的值移动到右侧分区中的另一个位置。由于在索引

   j

   处我们现在有空间容纳它，因此它被放置在那里。
回溯时，将数组恢复到交换之前的状态非常重要，因为在递归树的较高级别（其中

i

更小），存在依赖于这个不变量的循环：它们的

 j

不应遇到已在较早索引中处理过的值。因此我们希望将数组恢复到交换之前的状态，因此我们“取消交换”这两个值。我们可以确定这两个是在递归调用之前交换的两个相同的，因为通过这种取消交换，

each

递归调用将保证数组将恢复到调用之前的状态。 此取消交换

不是

，而是选择不同值。这仅发生在 j 循环的下一次迭代中。这次恢复只是为下一次迭代中的下一次替代选择做好准备。

没有

slate

您的实现的

slate

参数并不是真正需要的。由于输入数组用于存储两个分区，因此当您到达递归末尾时，排列将在该数组本身中表示，并且您只需将

that

数组的副本添加到结果集中即可。 此外，您可以通过将此函数转换为生成器来避免访问“外部”

result

变量。然后，调用者有责任将生成的排列收集到数组中——如果他们愿意的话。

最后，我会将

i

设置为

second

参数，这样你就可以给它一个默认值 0，并且初始调用者只需传递一个参数 - 要排列的值数组。 看起来是这样的：

function* dfs(nums, i=0) { // Rearranged parameters
    if (i === nums.length) {
        yield nums.slice(); // nums itself has the permutation!
        return;
    }

    for (let j = i; j < nums.length; j++) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        yield* dfs(nums, i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]]; // Backtrack: Restore original state
    }
}

// Example call
const result = [...dfs([1, 2, 3])];
console.log(result);