PHP回溯算法代码疑问：多次pop执行原因及索引逻辑解析

问题背景 #

我理解回溯算法的理论，但搞不懂对应的PHP代码逻辑。以下是实现数组全排列的回溯算法示例代码及运行输出：

function permute($nums)
{
    $result = array();
    backTracking($nums, count($nums), 0, array(), $result);
    return $result;
}

function backTracking($nums, $numsLength, $startIndex, $permutation, &$result)
{

    if (count($permutation) == $numsLength) {
        array_push($result, $permutation);
        print_r("return" . "\n");
        return;
    }

    for ($i = $startIndex; $i < $numsLength; $i++) {
        if (!in_array($nums[$i], $permutation)) {
            array_push($permutation, $nums[$i]);
            print_r($i . "\n");
            print_r($permutation);
            backTracking($nums, $numsLength, 0, $permutation, $result);
            print_r('pop : ' . array_pop($permutation) . "\n");
        }
    }
}


$nums = [1, 2, 3];
var_dump(permute($nums));

运行结果 #

0
Array
(
    [0] => 1
)
1
Array
(
    [0] => 1
    [1] => 2
)
2
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
)
return
pop : 3
pop : 2
2
Array
(
    [0] => 1
    [1] => 3
)
1
Array
(
    [0] => 1
    [1] => 3
    [2] => 2
)
return
pop : 2
pop : 3
pop : 1
1
Array
(
    [0] => 2
)
0
Array
(
    [0] => 2
    [1] => 1
)
2
Array
(
    [0] => 2
    [1] => 1
    [2] => 3
)
return
pop : 3
pop : 1
2
Array
(
    [0] => 2
    [1] => 3
)
0
Array
(
    [0] => 2
    [1] => 3
    [2] => 1
)
return
pop : 1
pop : 3
pop : 2
2
Array
(
    [0] => 3
)
0
Array
(
    [0] => 3
    [1] => 1
)
1
Array
(
    [0] => 3
    [1] => 1
    [2] => 2
)
return
pop : 2
pop : 1
1
Array
(
    [0] => 3
    [1] => 2
)
0
Array
(
    [0] => 3
    [1] => 2
    [2] => 1
)
return
pop : 1
pop : 2
pop : 3
array(6) {
  [0]=>
  array(3) {
    [0]=>
    int(1)
    [1]=>
    int(2)
    [2]=>
    int(3)
  }
  [1]=>
  array(3) {
    [0]=>
    int(1)
    [1]=>
    int(3)
    [2]=>
    int(2)
  }
  [2]=>
  array(3) {
    [0]=>
    int(2)
    [1]=>
    int(1)
    [2]=>
    int(3)
  }
  [3]=>
  array(3) {
    [0]=>
    int(2)
    [1]=>
    int(3)
    [2]=>
    int(1)
  }
  [4]=>
  array(3) {
    [0]=>
    int(3)
    [1]=>
    int(1)
    [2]=>
    int(2)
  }
  [5]=>
  array(3) {
    [0]=>
    int(3)
    [1]=>
    int(2)
    [2]=>
    int(1)
  }
}

我的疑问 #

1. 为什么函数会执行两次或三次pop操作？这是否取决于当前执行的栈帧数量？
2. 代码中的索引$i的取值逻辑是怎样的？

解答 #

关于pop操作的次数 #

pop操作的次数确实和当前的函数调用栈深度直接相关，本质是回溯算法的「撤销选择」逻辑：

每次调用backTracking前，我们会把当前元素push到$permutation里，进入更深一层的递归，尝试构建完整排列。当递归返回（不管是找到完整排列触发return，还是循环结束），必须把刚才push的元素pop出来，恢复到上一层的状态，这样才能尝试其他可能的选择。

举个输出里的例子：

2
Array([0] =>1,[1]=>2,[2]=>3)
return
pop :3
pop :2

• 当$permutation凑齐3个元素，触发return，回到上一层递归（对应[1,2,3]的调用栈），执行第一次pop去掉3，回到[1,2]的状态；
• 这一层的循环已经走到i=2，循环结束，继续回到更上层的递归（对应[1]的状态），执行第二次pop去掉2，回到[1]，这样才能继续尝试i=2的元素3，构建[1,3,...]的排列。

简单说：每一次push都对应一次pop，递归嵌套了几层，就会连续执行几次pop来逐层回溯到上一级状态。

关于索引$i的取值逻辑 #

$i的取值分两种场景，核心是控制每一层递归的遍历范围：

1. 第一层递归（初始调用）：$startIndex=0，所以$i从0到2遍历整个数组，依次选择1、2、3作为排列的第一个元素；
2. 后续递归（进入深层）：每次递归调用时传入的$startIndex=0，所以每一层都会从0开始遍历整个数组，但通过!in_array($nums[$i], $permutation)判断元素是否已经在当前排列里，避免重复选择。

要注意：这段代码的$startIndex在深层递归里被固定为0，是因为它用in_array来做去重判断，和常见的「交换元素+固定起始索引」的全排列写法不同。比如当已经选了1之后，深层递归遍历0到2时，会跳过1，只选2和3。

看输出细节：选了1之后，第二层递归$startIndex=0，但i=0时nums[0]=1已经在$permutation里，所以跳过，直到i=1选2；第三层递归同样i=0和i=1都被跳过，直到i=2选3。

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