Recursion & Backtracking Master Recap: Interview Cheatsheet

def backtrack(state, choices):
    # Base case
    if is_complete(state):
        record_solution(state)
        return

    # Pruning
    if should_prune(state): return

    # Explore choices
    for choice in get_choices(choices):
        if is_valid(state, choice):
            make_choice(state, choice)     # CHOOSE
            backtrack(state, choices)      # EXPLORE
            undo_choice(state, choice)     # UNCHOOSE

# Subsets
def subsets(nums):
    res = []
    def bt(i, cur):
        res.append(cur[:])
        for j in range(i, len(nums)):
            cur.append(nums[j]); bt(j+1, cur); cur.pop()
    bt(0, [])
    return res

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

# Combination Sum
def combinationSum(cands, target):
    cands.sort(); res = []
    def bt(i, cur, rem):
        if rem==0: res.append(cur[:]); return
        for j in range(i, len(cands)):
            if cands[j]>rem: break
            cur.append(cands[j]); bt(j, cur, rem-cands[j]); cur.pop()
    bt(0, [], target); return res

# N-Queens
def nQueens(n):
    res, cols, d1, d2 = [], set(), set(), set()
    board = [['.']*n for _ in range(n)]
    def bt(r):
        if r==n: res.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or r-c in d1 or r+c in d2: continue
            board[r][c]='Q'; cols.add(c); d1.add(r-c); d2.add(r+c)
            bt(r+1)
            board[r][c]='.'; cols.discard(c); d1.discard(r-c); d2.discard(r+c)
    bt(0); return res