尝试通过这个简单的例子来了解回溯是如何在 php 上工作的

Question

我试图了解回溯在 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)
  }
}

也许是一个简单的问题，但为什么该函数会循环两次或 3 次 pop？它取决于执行的帧数？进而;指数取决于什么？

谢谢大家！！

Answer 1

我终于找到了理解它的方法。我找到了一个网站，你可以用 python 编写代码，你可以检查每个堆栈，检查每个堆栈上发生了什么。

这是网站：

https://pythontutor.com/

同样的代码，但在Python中：

def find_nums(numbers: list, target: int) -> list:
    def find_num(start: int, target: int, combination: list):
        if target == 0:
            result.append(combination[:])
            return
        if target < 0 or target == len(numbers):
            return
        for index in range(start, len(numbers)):
            if index > start and numbers[index] == numbers[index-1]:
                continue
            combination.append(numbers[index])
            find_num(index + 1, target - numbers[index], combination)
            combination.pop()
    result = []
    find_num(0, target, [])
    return result


print(find_nums([1,2,3,5], 6))