Search code examples
swiftalgorithmpermutationdepth-first-searchbacktracking

Permutation- DFS and backtracking- need help in understanding unwinding and backtracking

The following code is used to implement a permutation of an array of Ints. I am not able to wrap my head around as to how the backtracking is being done here- especially after I print [1, 2, 3], how do I go back and print [1, 3, 2]- how exactly is the path.removeLast() working?

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()
    }
Solution

  • Sometimes it's easiest to understand backtracking with an example. Take the array [1,2,3], then using your approach you do something like this:

    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:

    Effectively what you're doing is generating all possible subsequences for every permutation and then removing them (hence remove last) till you get back to an empty list. If you drew the recursion tree for the code you provided, you would have 31 nodes (one for each line above). Can we do better? Yes. Consider the following tree for the same example: enter image description here

    (Prettier version of similar tree with chars instead of ints here: Permutation of string using backtracking algorithm)

    A big improvement. Only 10 nodes in the tree, and the last level in the tree has all the permutations. This can be accomplished using backtracking and is a far simpler example to comprehend. All you do is swap nodes instead of generating all possible subsequences for each permutation. A Swift implementation of this second, better approach can be found here: https://leetcode.com/problems/permutations/discuss/229627/Swift