Backtracking [Top-Down] [Recursion]

Description

Backtracking algorithm is a method to solve problems by exhaustive search. Its core concept is to start from an initial state and brutally search for all possible solutions. The algorithm records the correct ones until a solution is found or all possible solutions have been tried but no solution can be found.

Backtracking typically employs "depth-first search" to traverse the solution space.

Workflow

• Trial and retreat: It is called a backtracking algorithm because it uses a "trial" and "retreat" strategy when searching the solution space. During the search, whenever it encounters a state where it can no longer proceed to obtain a satisfying solution, it undoes the previous choice and reverts to the previous state so that other possible choices can be chosen for the next attempt.
• Prune: Complex backtracking problems usually involve one or more constraints, which are often used for "pruning".

Advantages & Limitations

The backtracking algorithm is essentially a depth-first search algorithm that attempts all possible solutions until a satisfying solution is found. The advantage of this method is that it can find all possible solutions, and with reasonable pruning operations, it can be highly efficient.

However, when dealing with large-scale or complex problems, the running efficiency of backtracking algorithm may not be acceptable.

• Time complexity: Backtracking algorithms usually need to traverse all possible states in the state space, which can reach exponential or factorial time complexity.
• Space complexity: In recursive calls, it is necessary to save the current state (such as paths, auxiliary variables for pruning, etc.). When the depth is very large, the space need may become significantly bigger.

Even so, backtracking remains the best solution for certain search problems and constraint satisfaction problems. For these problems, there is no way to predict which choices can generate valid solutions. We have to traverse all possible choices. In this case, the key is about how to optimize the efficiency. There are two common efficiency optimization methods.

• Prune: Avoid searching paths that definitely will not produce a solution, thus saving time and space.
• Heuristic search: Introduce some strategies or estimates during the search process to prioritize the paths that are most likely to produce valid solutions.

Use Cases

Backtracking algorithms can be used to solve many search problems, constraint satisfaction problems, and combinatorial optimization problems.

Example

def pre_order(root: TreeNode):
    if root is None:
        return

    # Attempt
    path.append(root)
    if root.val == 7:
        # Record solution
        res.append(list(path))

    pre_order(root.left)
    pre_order(root.right)

    # Retract
    path.pop()

def pre_order(root: TreeNode):
    if root is None:
        return

    # Pruning
    if root.val == 3:
        return

    # Attempt
    path.append(root)
    if root.val == 7:
        # Record solution
        res.append(list(path))

    pre_order(root.left)
    pre_order(root.right)

    # Retract
    path.pop()

def backtrack(state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]):
    # When the state length equals the number of elements, record the solution
    if len(state) == len(choices):
        res.append(list(state))
        return

    # Traverse all choices
    for i, choice in enumerate(choices):
        # Pruning: do not allow repeated selection of elements
        if not selected[i]:
            # Attempt: make a choice, update the state
            selected[i] = True
            state.append(choice)
            # Proceed to the next round of selection
            backtrack(state, choices, selected, res)
            # Retract: undo the choice, restore to the previous state
            selected[i] = False
            state.pop()

def permutations_i(nums: list[int]) -> list[list[int]]:
    """Permutation I"""
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res

def fibonacci(n, memo={}):
    # If result already computed, return it
    if n in memo:
        return memo[n]

    # Base cases
    if n <= 1:
        return n

    # Recursively compute and store result
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))  # Output: 55