swift - 排列 - DFS 和回溯 - 需要帮助理解展开和回溯

Question

以下代码用于实现 Int 数组的排列。我无法完全理解回溯是如何在这里完成的——尤其是在我打印 [1, 2, 3] 之后，我该如何返回并打印 [1 , 3, 2]- path.removeLast() 究竟是如何工作的？

func permute(_ nums: [Int]) -> [[Int]] {
    var res = [[Int]]()
    var path = [Int]()
    var isVisited = [Bool](repeating: false, count: nums.count)
    var counter = 0
    dfs(&res, &path, &isVisited, nums)

    return res
}

private func dfs(_ res: inout [[Int]], _ path: inout [Int], _ isVisited: inout [Bool], _ nums: [Int]) {
    guard path.count != nums.count else {
        res.append(path)
        return
    }

    for (i, num) in nums.enumerated() where !isVisited[i] {
        path.append(num)
        isVisited[i] = true
        dfs(&res, &path, &isVisited, nums)
        isVisited[i] = false
        path.removeLast()
    }

Answer 1

有时通过示例最容易理解回溯。获取数组 [1,2,3]，然后使用您的方法执行如下操作:

Before removing: 1
Before removing: 1 2
Before removing: 1 2 3
After removing: 1 2
After removing: 1
Before removing: 1 3
Before removing: 1 3 2
After removing: 1 3
After removing: 1
After removing:
Before removing: 2
Before removing: 2 1
Before removing: 2 1 3
After removing: 2 1
After removing: 2
Before removing: 2 3
Before removing: 2 3 1
After removing: 2 3
After removing: 2
After removing:
Before removing: 3
Before removing: 3 1
Before removing: 3 1 2
After removing: 3 1
After removing: 3
Before removing: 3 2
Before removing: 3 2 1
After removing: 3 2
After removing: 3
After removing:

实际上，您所做的是为每个排列生成所有可能的子序列，然后删除它们(因此删除最后一个)，直到您返回一个空列表。如果为您提供的代码绘制递归树，您将有 31 个节点(上面的每一行一个)。我们能做得更好吗？是的。对于同一示例，请考虑以下树:

(类似树的更漂亮版本，这里使用字符而不是整数:Permutation of string using backtracking algorithm)

一个很大的改进。树中只有 10 个节点，树中的最后一层包含所有排列。这可以使用回溯来完成，并且是一个更容易理解的例子。您所做的只是交换节点，而不是为每个排列生成所有可能的子序列。第二种更好方法的 Swift 实现可以在这里找到:https://leetcode.com/problems/permutations/discuss/229627/Swift