Recursion and Backtracking

Recursion and Backtracking

# Backtracking: explore, check, undo

# Subsets (power set)
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i+1, current)
            current.pop()  # UNDO
    backtrack(0, [])
    return result

# Permutations
def permute(nums):
    result = []
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:]); return
        for i,n in enumerate(nums):
            if used[i]: continue
            used[i] = True
            path.append(n)
            backtrack(path, used)
            path.pop()
            used[i] = False
    backtrack([], [False]*len(nums))
    return result

# Memoisation -- top-down DP
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)