Backtracking

Definition

Backtracking builds a solution step by step and undoes a choice when it cannot lead to a valid answer.

Solves permutations, subsets, N-Queens and Sudoku.

Diagram

Flowchart

Example: All subsets

def subsets(nums):
    res = []
    def go(i, cur):
        if i == len(nums):
            res.append(cur[:]); return
        cur.append(nums[i]); go(i + 1, cur)
        cur.pop(); go(i + 1, cur)
    go(0, [])
    return res
print(len(subsets([1, 2, 3])))

Output: 8

Complexity

Often exponential: subsets O(2ⁿ), permutations O(n!)

Key points

• Prune early to save time
• Always undo the choice after recursion

Interview questions

More DSA topics