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

Question

以下代码用于实现Ints数组的排列。我无法围绕如何在这里完成回溯 - 特别是在我打印[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