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.

Backtracking can be applied only for problems which admit the concept of a “partial candidate solution” and a relatively quick test of whether it can possibly be completed to a valid solution.

Backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles.

Here is a template for backtracking approach:

def backtrack(curr, OTHER_ARGUMENTS...):
    if (BASE_CASE):
        # modify the answer
        return

    ans = 0
    for (ITERATE_OVER_INPUT):
        # modify the current state
        ans += backtrack(curr, OTHER_ARGUMENTS...)
        # undo the modification of the current state

    return ans

permutations(nums: List[int]) → List[List[int]]

Given a collection of distinct integers, return all possible permutations.

Time complexity: \(O(n!)\)

Space complexity: \(O(n!)\)

combinationSum(k, n)

Problem: Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Time complexity: \(O(9^k)\)

Space complexity: \(O(9^k)\)

nCastles(n)

Problem: Given a chessboard of size n x n, find all possible positions to place n castles such that no two castles attack each other.

Time complexity: \(O(n!)\)

Space complexity: \(O(n!)\)

nQueens(n: int) → List[List[str]]

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. Problem: Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

Time complexity: \(O(n!)\)

Space complexity: \(O(n!)\)