Chapter 12. Backtracking

Chapter 12. Backtracking#

Backtracking is similar to DFS, and a greedy approach. The difference between backtracing and DFS is backtracking algorithm traverses the branch of a recursion tree, while DFS traverses the node of the recursion tree.

Backtrack is typically used for a problem that requires 1) all possible solutions, 2) no duplicated subproblems, such as permutation, N-Queen problem.

1. Template#

The code template of backtrack follows:

result = []
def backtrack(paths, choices):
    # if terminal conditions are met, then update results
    if terminal:
        result.add(paths)
        return

    for choice in choices:
        # do the choice, update paths and choices
        do(choice)
        # backtrack
        backtrack(paths, choices)
        # undo the choice, go back to previous paths and choices
        undo(choice)

2. Permutation#

Given an array nums, return the permutations of all the number. We can assume there is no duplicated number in nums, such as nums=[1,2,3]

  • path: current path of traversing the numbers, such as [1]

  • choices: the available choices on the current path. For example, on the path [1], we can choose 2, or 3 next.

Leetcode:

  • 0046

def permutation(nums):
    res = []
    def backtrack(path, choices):
        if not choices:
            # we have to use path[:] to copy the path, otherwise the path will be changed after pop()
            res.append(path[:])
            return
        for i in range(len(choices)):
            path += [choices[i]]
            backtrack(path, choices[:i]+choices[i+1:])
            path.pop()

    backtrack([], nums)
    return res

# test
nums = [1,2,3]
print(permutation(nums))

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

3. N-Queen Problem#

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

  • path: current path of putting Q on the row

  • choice: choice of putting Q on the column

Leetcode:

  • 0051

def solveQueen(n):
    res = []
    def isValid(path, choice):
        for i in range(len(path)):
            if path[i] == choice or abs(path[i] - choice) == abs(i - len(path)):
                return False
        return True
    
    def backtrack(path, choices):
        if len(path) == n:
            res.append(path[:])
            return
        for choice in choices:
            if isValid(path, choice):
                path.append(choice)
                backtrack(path, choices)
                path.pop()

    backtrack([], range(n))
    return res

# test
n = 1
print(solveQueen(n))

n = 4
print(solveQueen(n))

n = 5
print(solveQueen(n))

[[0]]
[[1, 3, 0, 2], [2, 0, 3, 1]]
[[0, 2, 4, 1, 3], [0, 3, 1, 4, 2], [1, 3, 0, 2, 4], [1, 4, 2, 0, 3], [2, 0, 3, 1, 4], [2, 4, 1, 3, 0], [3, 0, 2, 4, 1], [3, 1, 4, 2, 0], [4, 1, 3, 0, 2], [4, 2, 0, 3, 1]]

Reference#

[1] https://labuladong.github.io/algo/di-san-zha-24031/bao-li-sou-96f79/hui-su-sua-c26da/.

Contents