What is backtracking?

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Essentially, backtracking is dfs on a tree of possible solutions.

Backtracking template

For a general backtracking, we need to write a base case for the end condition, a loop for the choices, and a recursive call.

def backtrack(path, choices):
    if end_condition(path):
        res.append(path)
        return
    for choice in choices:
        if is_valid(path, choice):
            path.add(choice)
            backtrack(path, choices)
            path.remove(choice)

You can remove the path.add(choice) and path.remove(choice) if you just add the choice to the path in the recursive call.

backtrack(path + [choice], choices)

There are many variations of backtracking, such as the subset sum problem, n-queens problem, and sudoku.

Variations

We can moidy the template to fit different problems.

Permutations

For permutations, we need to add a visited set to keep track of the visited elements.

def backtrack(path, choices, visited):
    if end_condition(path):
        res.append(path)
        return
    for choice in choices:
        if is_valid(path, choice):
            path.add(choice)
            visited.add(choice)
            backtrack(path, choices, visited)
            path.remove(choice)
            visited.remove(choice)

Combinations

For combinations, we need to add a start index to avoid duplicates.

def backtrack(path, choices, start):
    if end_condition(path):
        res.append(path)
        return
    for i in range(start, len(choices)):
        if is_valid(path, choices[i]):
            path.add(choices[i])
            backtrack(path, choices, i + 1)
            path.remove(choices[i])

Duplicated input

For duplicated input, we need to sort the input and skip the duplicated elements.

def backtrack(path, choices, start):
    if end_condition(path):
        res.append(path)
        return
    for i in range(start, len(choices)):
        if i > start and choices[i] == choices[i - 1]:
            continue
        if is_valid(path, choices[i]):
            path.add(choices[i])
            backtrack(path, choices, i + 1)
            path.remove(choices[i])

Multiple solutions on one path(Subsets)

For subsets, we need to add the result to the result list, and we do not need to check the end condition.

def backtrack(path, choices, start):
    result.add(path)
    for i in range(start, len(choices)):
        if is_valid(path, choices[i]):
            path.add(choices[i])
            backtrack(path, choices, i + 1, result)
            path.remove(choices[i])