Recursion & Backtracking

Concept

A recursive function needs a base case (when to stop) and a recursive case that moves towards the base case.

Backtracking builds a solution step by step: choose, explore, then un-choose. It generates subsets, permutations and solves puzzles like N-Queens.

Each call uses a stack frame, so deep recursion costs O(depth) space.

Complexity

Code (Python)

def subsets(nums):
    res, path = [], []
    def dfs(i):
        if i == len(nums):
            res.append(path[:])
            return
        path.append(nums[i])   # choose
        dfs(i + 1)             # explore
        path.pop()             # un-choose
        dfs(i + 1)
    dfs(0)
    return res

Remember

• Always write the base case first.
• Copy the path when saving a result.
• Prune early to cut the search tree.