通过回溯了解排列

Question

我正在尝试弄清楚以下回溯解决方案如何生成以列表形式给出的所有整数排列：

def permutations(arr):
    res = []
    backtrack(arr, [], set(), res)
    print(res)

def backtrack(arr, temp, visited, res):
    if len(temp) == len(arr):
        res.append(temp[:])
    else:
        for num in arr:
            if num in visited: continue
            visited.add(num)
            temp.append(num)
            backtrack(arr, temp, visited, res)
            visited.remove(num)
            temp.pop()

正在执行以下操作：

permutations([1, 2, 3])

结果符合预期：

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

我不明白的是循环结束时的 temp.pop() 调用。我知道 pop() 会丢弃列表的最后一个元素，但为什么这里有必要？

如果有人能向我解释一下，我将不胜感激。

Answer 1

这是必要的，因为在下一次迭代中，该函数将再次 append 一个元素，因此如果您事先没有 pop ，列表的大小将继续增长。由于 backtrack 仅在 temp 的长度等于原始 arr 的长度时才添加结果，因此它不会添加超出第一个排列 [1, 2, 3] 的任何内容（因为从那里开始， temp 列表不断增加）。

我们可以删除该行 (temp.pop()) 并查看结果：

[[1, 2, 3]]

现在，如果我们还更改每当 len(temp) >= len(arr) 时添加结果，那么我们将看到 temp 的大小如何增长：

[[1, 2, 3], [1, 2, 3, 3], [1, 2, 3, 3, 2], [1, 2, 3, 3, 2, 3]]

我们在这里得到的结果较少，因为对于超出 [1, 2, 3] 的每个递归调用，都会立即复制 temp 列表，而不会到达 for 循环。

通过回溯了解排列

Understanding permutations with backtracking

python

permutation

backtracking