Backtracking

Backtracking is an algorithmic technique that considers searching every possible combination in order to solve a computational problem. It builds candidates to the solution incrementally and abandons candidates ("backtracks") when it determines that the candidate cannot lead to a valid solution.

Time Complexity: Usually $O(2^n)$ or $O(n!)$ depending on the problem

Space Complexity: $O(n)$ for recursion stack

Template

Python

def backtrack(candidates: list, path: list, result: list):
    if condition:
        result.append(path[:])
        return
    for candidate in candidates:
        path.append(candidate)
        backtrack(candidates, path, result)
        path.pop()  # "backtrack" = remove the last appended element

Example: Subsets

Here's an example of generating all possible subsets of a set using backtracking.

• condition: The stop condition in this case is when the length of the path is equal to the length of the candidates, indicating that a complete subset (the whole set) has been formed.
• candidates: The set of elements to generate subsets from.
• path: The current subset being built.
• result: The list of all subsets.

Python

def backtrack(candidates: list, path: list, result: list):
    if len(path) == len(candidates):
        result.append(path[:])
        return
    for candidate in candidates:
        path.append(candidate)
        backtrack(candidates, path, result)
        path.pop()  # "backtrack" = remove the last appended element


def subsets(candidates: list):
    result = []  # To be mutated
    backtrack(candidates, [], result)
    return result


# Example usage
candidates = [1, 2, 3]
result = subsets(candidates)