Recursion

1. Break down into smaller scopes: x₀, x₁, ..., xₙ ∈ X
2. Recursively solve: F(x₀), F(x₁), ..., F(xₙ)
3. Combine results to solve F(X)

        fib(5)
       /      \
    fib(4)    fib(3)
    /    \     /    \
fib(3)  fib(2) fib(2) fib(1)
 /   \    /  \   /  \
fib(2) fib(1) fib(1) fib(0)
 /   \
fib(1) fib(0)

# Example: LC 22 (Generate Parentheses)
_list = ["(", ")"]
for x in _list:
    _tmp = tmp + x
    help(_tmp)

def topDown(node, parentInfo):
    # Base case
    if not node:
        return baseResult

    # Use parentInfo to make decision
    currentResult = processWithParentInfo(node, parentInfo)

    # Pass updated info to children
    newParentInfo = updateParentInfo(parentInfo, node)
    leftResult = topDown(node.left, newParentInfo)
    rightResult = topDown(node.right, newParentInfo)

    # Combine results
    return combineResults(currentResult, leftResult, rightResult)

def hasPathSum(self, root, targetSum):
    def topDown(node, currentSum):
        if not node:
            return False

        currentSum += node.val

        # Leaf node check
        if not node.left and not node.right:
            return currentSum == targetSum

        # Continue to children with updated sum
        return (topDown(node.left, currentSum) or
                topDown(node.right, currentSum))

    return topDown(root, 0)

def bottomUp(node):
    # Base case
    if not node:
        return baseResult

    # Get results from children first
    leftResult = bottomUp(node.left)
    rightResult = bottomUp(node.right)

    # Process current node using children results
    currentResult = processNode(node, leftResult, rightResult)

    return currentResult

def maxDepth(self, root):
    def bottomUp(node):
        if not node:
            return 0

        # Get depths from children
        leftDepth = bottomUp(node.left)
        rightDepth = bottomUp(node.right)

        # Current depth is max of children + 1
        return max(leftDepth, rightDepth) + 1

    return bottomUp(root)

def isBalanced(self, root):
    def bottomUp(node):
        if not node:
            return True, 0  # (isBalanced, height)

        # Check left subtree
        leftBalanced, leftHeight = bottomUp(node.left)
        if not leftBalanced:
            return False, 0

        # Check right subtree
        rightBalanced, rightHeight = bottomUp(node.right)
        if not rightBalanced:
            return False, 0

        # Check current node balance
        isCurrentBalanced = abs(leftHeight - rightHeight) <= 1
        currentHeight = max(leftHeight, rightHeight) + 1

        return isCurrentBalanced, currentHeight

    balanced, _ = bottomUp(root)
    return balanced

// LC 404 - Sum of Left Leaves
// IDEA: Pre-order traversal, pass isLeft flag to track if node is left child
private int processSubtree(TreeNode subtree, boolean isLeft) {
    // Base case: empty subtree
    if (subtree == null) {
        return 0;
    }

    // Base case: leaf node
    if (subtree.left == null && subtree.right == null) {
        return isLeft ? subtree.val : 0;
    }

    // Recursive case: process left and right subtrees
    return processSubtree(subtree.left, true) + processSubtree(subtree.right, false);
}

// LC 572 - Subtree of Another Tree
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    // Check if subtree rooted at 'root' matches 'subRoot'
    // Use OR: if ANY recursive call returns true, short-circuit and return true
    return isSameTree(root, subRoot) 
        || isSubtree(root.left, subRoot) 
        || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode node1, TreeNode node2) {
    if (node1 == null || node2 == null) {
        return node1 == null && node2 == null;
    }
    return node1.val == node2.val 
        && isSameTree(node1.left, node2.left) 
        && isSameTree(node1.right, node2.right);
}

1. Pick each element i in [start, end] as the "root" / split point
2. Recursively build all left results from [start, i-1]
3. Recursively build all right results from [i+1, end]
4. Cartesian product: for each left × right, construct and collect result
5. Base case: empty range → return [null/None] (one empty result, NOT empty list)

// Template: Recursive Construction via Cartesian Product
private List<TreeNode> build(int start, int end) {
    List<TreeNode> res = new ArrayList<>();
    if (start > end) {
        res.add(null);  // CRITICAL: null = valid empty subtree
        return res;
    }
    for (int i = start; i <= end; i++) {
        List<TreeNode> lefts = build(start, i - 1);
        List<TreeNode> rights = build(i + 1, end);
        for (TreeNode l : lefts)
            for (TreeNode r : rights)
                res.add(new TreeNode(i, l, r));
    }
    return res;
}

def generateTrees(n):
    if n == 0: return []
    def generate(start, end):
        if start > end:
            return [None]
        all_trees = []
        for i in range(start, end + 1):
            for left in generate(start, i - 1):
                for right in generate(i + 1, end):
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    all_trees.append(root)
        return all_trees
    return generate(1, n)

# Without memoization: O(2^n) — exponential
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# With memoization: O(n) — linear
def fibonacci(n):
    cache = {}
    def helper(n):
        if n in cache:
            return cache[n]
        if n < 2:
            res = n
        else:
            res = helper(n - 1) + helper(n - 2)
        cache[n] = res
        return res
    return helper(n)

# Without memoization: O(2^n)
class Solution:
    def climbStairs(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

# With memoization: O(n)
class Solution:
    def climbStairs(self, n):
        cache = {}
        def helper(n):
            if n in cache:
                return cache[n]
            if n <= 2:
                res = n
            else:
                res = helper(n - 2) + helper(n - 1)
            cache[n] = res
            return res
        return helper(n)

1. Divide: Split problem into subproblems
2. Conquer: Solve each subproblem recursively
3. Combine: Merge subproblem results

def divide_and_conquer(problem):
    # (1) Divide
    subproblems = divide(problem)
    
    # (2) Conquer
    results = [divide_and_conquer(sub) for sub in subproblems]
    
    # (3) Combine
    return combine(results)

1. Use a stack or queue to replace the system call stack
2. At each recursion point, push parameters onto data structure
3. Replace recursive chain with loop over the data structure

class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        return self.mirror(root.left, root.right)

    def mirror(self, left, right):
        if not left or not right:
            return left == right
        if left.val != right.val:
            return False
        return self.mirror(left.left, right.right) and self.mirror(left.right, right.left)

class Solution:
    def isOneEditDistance(self, s, t):
        m, n = len(s), len(t)
        if abs(m - n) > 1:
            return False
        if m > n:
            return self.isOneEditDistance(t, s)
        for i in range(m):
            if s[i] != t[i]:
                if m == n:
                    return s[i + 1:] == t[i + 1:]
                return s[i:] == t[i + 1:]
        return m != n

class Solution:
    def mergeTwoLists(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

class Solution:
    def isSubtree(self, root, subRoot):
        def isSameTree(p, q):
            if not p and not q:
                return True
            if not p or not q:
                return False
            return (p.val == q.val and 
                    isSameTree(p.left, q.left) and 
                    isSameTree(p.right, q.right))
        
        if not root and not subRoot:
            return True
        if not root or not subRoot:
            return False
        # Use OR: if any recursive call returns True, stop early
        return (isSameTree(root, subRoot) or 
                self.isSubtree(root.left, subRoot) or 
                self.isSubtree(root.right, subRoot))

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return false;
    }
    if (isIdentical(root, subRoot)) {
        return true;
    }
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isIdentical(TreeNode node1, TreeNode node2) {
    if (node1 == null || node2 == null) {
        return node1 == null && node2 == null;
    }
    return node1.val == node2.val && 
           isIdentical(node1.left, node2.left) && 
           isIdentical(node1.right, node2.right);
}

1. Base case   : list too short to change -> return head unchanged
2. Recurse     : newTail/rest = f(<node further down the list>)
3. Rewire      : fix current node's `next`, then RETURN the node that is now first

// java
// LC 206 - Reverse Linked List
// IDEA: recursion returns the NEW head; on the way back up, make my successor point at me
// time = O(n), space = O(n) (call stack)
public ListNode reverseList(ListNode head) {
    // base: empty or single node -> already reversed
    if (head == null || head.next == null) return head;

    ListNode newHead = reverseList(head.next); // newHead = tail of original list
    head.next.next = head;                     // successor now points back at me
    head.next = null;                          // CRITICAL: cut old link, else cycle
    return newHead;                            // head never changes going back up
}

# python
# LC 206 - Reverse Linked List
# IDEA: recursion returns the NEW head; on the way back up, make my successor point at me
# time = O(n), space = O(n) (call stack)
def reverseList(head):
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None      # CRITICAL: cut old link, else cycle
    return new_head

// java
// LC 24 - Swap Nodes in Pairs
// IDEA: swap the first two nodes, recurse on the rest, return the 2nd node as new head
// time = O(n), space = O(n)
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head; // 0 or 1 node left

    ListNode second = head.next;
    head.next = swapPairs(second.next); // rest of list, already swapped
    second.next = head;
    return second;                      // second is now the head of this pair
}

# python
# LC 24 - Swap Nodes in Pairs
# IDEA: swap the first two nodes, recurse on the rest, return the 2nd node as new head
# time = O(n), space = O(n)
def swapPairs(head):
    if not head or not head.next:
        return head
    second = head.next
    head.next = swapPairs(second.next)
    second.next = head
    return second

// java
// LC 25 - Reverse Nodes in k-Group
// IDEA: probe k nodes ahead; if a full group exists, recurse on the remainder FIRST,
//       then reverse this group with the recursive result as its new tail
// time = O(n), space = O(n/k) recursion depth
public ListNode reverseKGroup(ListNode head, int k) {
    // step 1: is there a full group of k? if not, leave the tail untouched
    ListNode node = head;
    for (int i = 0; i < k; i++) {
        if (node == null) return head;
        node = node.next;
    }
    // node = (k+1)-th node = start of the remainder

    // step 2: solve the remainder first, it becomes what this group points to
    ListNode prev = reverseKGroup(node, k);

    // step 3: standard iterative reverse of exactly k nodes onto `prev`
    ListNode cur = head;
    for (int i = 0; i < k; i++) {
        ListNode nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev; // prev = k-th node = new head of this group
}

# python
# LC 25 - Reverse Nodes in k-Group
# IDEA: probe k nodes ahead; if a full group exists, recurse on the remainder FIRST,
#       then reverse this group with the recursive result as its new tail
# time = O(n), space = O(n/k) recursion depth
def reverseKGroup(head, k):
    node = head
    for _ in range(k):
        if not node:
            return head          # fewer than k nodes left -> keep as-is
        node = node.next

    prev = reverseKGroup(node, k)  # reversed remainder
    cur = head
    for _ in range(k):
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

// java
// LC 203 - Remove Linked List Elements
// IDEA: clean the rest first, then decide whether to keep myself
// time = O(n), space = O(n)
public ListNode removeElements(ListNode head, int val) {
    if (head == null) return null;
    head.next = removeElements(head.next, val);
    return head.val == val ? head.next : head; // skip myself if I match
}

// java
// LC 234 - Palindrome Linked List
// IDEA: recursion unwinds back-to-front; `front` pointer moves front-to-back in lockstep
// time = O(n), space = O(n) (O(1) space alternative: reverse the 2nd half iteratively)
private ListNode front;
public boolean isPalindrome(ListNode head) {
    front = head;
    return check(head);
}
private boolean check(ListNode node) {
    if (node == null) return true;
    if (!check(node.next)) return false; // go to the end first
    if (node.val != front.val) return false;
    front = front.next;                  // compare back-node vs front-node
    return true;
}

# python
# LC 234 - Palindrome Linked List
# IDEA: recursion unwinds back-to-front; `front` pointer moves front-to-back in lockstep
# time = O(n), space = O(n)
def isPalindrome(head):
    front = head
    def check(node):
        nonlocal front
        if not node:
            return True
        if not check(node.next):
            return False
        if node.val != front.val:
            return False
        front = front.next
        return True
    return check(head)

1. Keep the cursor OUTSIDE the recursion (field in Java, `nonlocal` in Python).
   Passing `int i` by value does not work - the caller must see how far the callee ate.
2. One function per grammar rule; each one:
     - reads the tokens of its own rule
     - recurses at the nesting point ('(' , '[' , a sub-expression)
     - returns its value with the cursor sitting on the NEXT unconsumed char
3. Be explicit about who consumes the closing delimiter (pick a convention, keep it).

// java
// LC 394 - Decode String
// IDEA: recursive descent with a shared cursor; each call handles ONE bracket level
// time = O(total output length), space = O(nesting depth)
private int i = 0;

public String decodeString(String s) {
    i = 0;
    return parse(s);
}

// parses until end-of-string or the ']' that closes the current level
private String parse(String s) {
    StringBuilder sb = new StringBuilder();
    while (i < s.length() && s.charAt(i) != ']') {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            int k = 0;
            while (Character.isDigit(s.charAt(i))) {   // multi-digit repeat count
                k = k * 10 + (s.charAt(i) - '0');
                i++;
            }
            i++;                        // consume '['
            String inner = parse(s);    // recurse: body of this bracket
            i++;                        // consume ']'
            for (int t = 0; t < k; t++) sb.append(inner);
        } else {
            sb.append(c);
            i++;
        }
    }
    return sb.toString();
}

# python
# LC 394 - Decode String
# IDEA: recursive descent with a shared cursor; each call handles ONE bracket level
# time = O(total output length), space = O(nesting depth)
def decodeString(s):
    i = 0

    def parse():
        nonlocal i
        out = []
        while i < len(s) and s[i] != "]":
            if s[i].isdigit():
                k = 0
                while s[i].isdigit():          # multi-digit repeat count
                    k = k * 10 + int(s[i]); i += 1
                i += 1                          # consume '['
                inner = parse()                 # recurse: body of this bracket
                i += 1                          # consume ']'
                out.append(inner * k)
            else:
                out.append(s[i]); i += 1
        return "".join(out)

    return parse()

expr := term (('+' | '-') term)*
term := number | '(' expr ')' | '-' term      # unary minus, e.g. "-(3+4)"

// java
// LC 224 - Basic Calculator
// IDEA: one function per grammar rule; expr <-> term is mutual recursion, '(' re-enters expr
// time = O(n), space = O(paren depth)
private int p = 0;

public int calculate(String s) {
    p = 0;
    return expr(s);
}

private int expr(String s) {           // left-to-right +/- chain
    int res = term(s);
    while (true) {
        skipSpace(s);
        if (p >= s.length()) break;
        char c = s.charAt(p);
        if (c == '+')      { p++; res += term(s); }
        else if (c == '-') { p++; res -= term(s); }
        else break;                    // hit ')' -> let the caller consume it
    }
    return res;
}

private int term(String s) {           // number | '(' expr ')' | unary minus
    skipSpace(s);
    char c = s.charAt(p);
    if (c == '(') {
        p++;                           // consume '('
        int v = expr(s);               // mutual recursion
        skipSpace(s);
        p++;                           // consume ')'
        return v;
    }
    if (c == '-') { p++; return -term(s); }
    int v = 0;
    while (p < s.length() && Character.isDigit(s.charAt(p))) {
        v = v * 10 + (s.charAt(p) - '0');
        p++;
    }
    return v;
}

private void skipSpace(String s) {
    while (p < s.length() && s.charAt(p) == ' ') p++;
}

# python
# LC 224 - Basic Calculator
# IDEA: one function per grammar rule; expr <-> term is mutual recursion, '(' re-enters expr
# time = O(n), space = O(paren depth)
def calculate(s):
    i = 0

    def skip_space():
        nonlocal i
        while i < len(s) and s[i] == " ":
            i += 1

    def expr():                       # term (('+'|'-') term)*
        nonlocal i
        res = term()
        while True:
            skip_space()
            if i >= len(s):
                break
            if s[i] == "+":
                i += 1; res += term()
            elif s[i] == "-":
                i += 1; res -= term()
            else:
                break                 # ')' -> caller consumes it
        return res

    def term():                       # number | '(' expr ')' | '-' term
        nonlocal i
        skip_space()
        if s[i] == "(":
            i += 1
            v = expr()
            skip_space()
            i += 1
            return v
        if s[i] == "-":
            i += 1
            return -term()
        v = 0
        while i < len(s) and s[i].isdigit():
            v = v * 10 + int(s[i]); i += 1
        return v

    return expr()

x^n = (x^(n/2))^2            if n is even
x^n = (x^(n/2))^2 * x        if n is odd
x^0 = 1                      base case

// java
// LC 50 - Pow(x, n)
// IDEA: binary exponentiation - halve the exponent every call, square the result
// time = O(log n), space = O(log n)
public double myPow(double x, int n) {
    long N = n;                     // widen: -Integer.MIN_VALUE overflows an int
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    return fastPow(x, N);
}

private double fastPow(double x, long n) {
    if (n == 0) return 1.0;
    double half = fastPow(x, n / 2);   // compute ONCE
    return (n % 2 == 0) ? half * half : half * half * x;
}

# python
# LC 50 - Pow(x, n)
# IDEA: binary exponentiation - halve the exponent every call, square the result
# time = O(log n), space = O(log n)
def myPow(x, n):
    if n < 0:
        x, n = 1 / x, -n

    def fast(x, n):
        if n == 0:
            return 1.0
        half = fast(x, n // 2)          # compute ONCE
        return half * half if n % 2 == 0 else half * half * x

    return fast(x, n)

// java
// LC 1922 - Count Good Numbers
// IDEA: modular fast power; ceil(n/2) even slots x 5 choices, floor(n/2) odd slots x 4
// time = O(log n), space = O(log n)
private static final int MOD = 1_000_000_007;

public int countGoodNumbers(long n) {
    return (int) (powMod(5, (n + 1) / 2) * powMod(4, n / 2) % MOD);
}

private long powMod(long b, long e) {
    if (e == 0) return 1;
    long half = powMod(b, e / 2);
    long sq = half * half % MOD;
    return (e % 2 == 0) ? sq : sq * b % MOD;
}

# python
# LC 1922 - Count Good Numbers
# IDEA: modular fast power; ceil(n/2) even slots x 5 choices, floor(n/2) odd slots x 4
# time = O(log n), space = O(log n)
def countGoodNumbers(n):
    MOD = 10 ** 9 + 7

    def pow_mod(b, e):
        if e == 0:
            return 1
        half = pow_mod(b, e // 2)
        sq = half * half % MOD
        return sq if e % 2 == 0 else sq * b % MOD

    return pow_mod(5, (n + 1) // 2) * pow_mod(4, n // 2) % MOD

// java
// LC 326 - Power of Three (same shape for LC 231 base 2, LC 342 base 4)
// IDEA: peel one factor per call; n is a power of b iff it divides down to exactly 1
// time = O(log n), space = O(log n)
public boolean isPowerOfThree(int n) {
    if (n < 1) return false;   // 0 and negatives are never powers
    if (n == 1) return true;   // 3^0
    return n % 3 == 0 && isPowerOfThree(n / 3);
}

# python
# LC 326 - Power of Three (same shape for LC 231 base 2, LC 342 base 4)
# IDEA: peel one factor per call; n is a power of b iff it divides down to exactly 1
# time = O(log n), space = O(log n)
def isPowerOfThree(n):
    if n < 1:
        return False
    if n == 1:
        return True
    return n % 3 == 0 and isPowerOfThree(n // 3)

1. Write out the answer for n = 1, 2, 3, 4 by hand.
2. Ask: "given the answer for n-1, what single operation produces the answer for n?"
   - index mapping   -> which position in row n-1 does position k in row n come from?
   - shift/rotation  -> after one round, what does the smaller problem's answer become?
3. Base case = the smallest n you can answer without thinking.

// java
// LC 779 - K-th Symbol in Grammar
// IDEA: position k of row n comes from position (k+1)/2 of row n-1; even k flips the bit
// time = O(n), space = O(n)
public int kthGrammar(int n, int k) {
    if (n == 1) return 0;                            // row 1 is just "0"
    int parent = kthGrammar(n - 1, (k + 1) / 2);
    return (k % 2 == 1) ? parent : 1 - parent;       // odd = copy, even = flip
}

# python
# LC 779 - K-th Symbol in Grammar
# IDEA: position k of row n comes from position (k+1)//2 of row n-1; even k flips the bit
# time = O(n), space = O(n)
def kthGrammar(n, k):
    if n == 1:
        return 0
    parent = kthGrammar(n - 1, (k + 1) // 2)
    return parent if k % 2 == 1 else 1 - parent

// java
// LC 1823 - Find the Winner of the Circular Game
// IDEA: Josephus recurrence (0-indexed): f(1) = 0, f(n) = (f(n-1) + k) % n
// time = O(n), space = O(n)
public int findTheWinner(int n, int k) {
    return winner(n, k) + 1;              // convert 0-indexed seat to 1-indexed
}

private int winner(int n, int k) {
    if (n == 1) return 0;
    return (winner(n - 1, k) + k) % n;    // shift the smaller answer by k
}

# python
# LC 1823 - Find the Winner of the Circular Game
# IDEA: Josephus recurrence (0-indexed): f(1) = 0, f(n) = (f(n-1) + k) % n
# time = O(n), space = O(n)
def findTheWinner(n, k):
    def winner(m):
        if m == 1:
            return 0
        return (winner(m - 1) + k) % m
    return winner(n) + 1

// java
// LC 273 - Integer to English Words
// IDEA: split off the biggest unit, name it, recurse on the remainder; helper always
//       returns a space-terminated chunk so concatenation is uniform
// time = O(log10(n)), space = O(log10(n))
private static final String[] BELOW_20 = {"", "One", "Two", "Three", "Four", "Five", "Six",
        "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
        "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty",
        "Sixty", "Seventy", "Eighty", "Ninety"};

public String numberToWords(int num) {
    if (num == 0) return "Zero";          // only place "Zero" is ever printed
    return words(num).trim();
}

private String words(int num) {
    if (num == 0)         return "";
    if (num < 20)         return BELOW_20[num] + " ";
    if (num < 100)        return TENS[num / 10] + " " + words(num % 10);
    if (num < 1000)       return BELOW_20[num / 100] + " Hundred " + words(num % 100);
    if (num < 1000000)    return words(num / 1000) + "Thousand " + words(num % 1000);
    if (num < 1000000000) return words(num / 1000000) + "Million " + words(num % 1000000);
    return words(num / 1000000000) + "Billion " + words(num % 1000000000);
}

# python
# LC 273 - Integer to English Words
# IDEA: split off the biggest unit, name it, recurse on the remainder; helper always
#       returns a space-terminated chunk so concatenation is uniform
# time = O(log10(n)), space = O(log10(n))
BELOW_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine",
            "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
            "Seventeen", "Eighteen", "Nineteen"]
TENS = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty",
        "Ninety"]

def numberToWords(num):
    if num == 0:
        return "Zero"

    def words(n):
        if n == 0:
            return ""
        if n < 20:
            return BELOW_20[n] + " "
        if n < 100:
            return TENS[n // 10] + " " + words(n % 10)
        if n < 1000:
            return BELOW_20[n // 100] + " Hundred " + words(n % 100)
        if n < 10 ** 6:
            return words(n // 1000) + "Thousand " + words(n % 1000)
        if n < 10 ** 9:
            return words(n // 10 ** 6) + "Million " + words(n % 10 ** 6)
        return words(n // 10 ** 9) + "Billion " + words(n % 10 ** 9)

    return words(num).strip()

move(n, src, dst, buf):
    move(n-1, src, buf, dst)      # clear the top n-1 out of the way — dst is now the buffer
    move disk n: src -> dst       # the one move you actually know how to make
    move(n-1, buf, dst, src)      # bring them back on top — src is now the buffer

# python
# Towers of Hanoi (CtCI 8.6) - move n disks from src to dst via buf, never putting
# a larger disk on a smaller one
# IDEA: the three pegs swap roles between the two recursive calls; that rotation,
#       not the move itself, is what makes the recursion correct
# time = O(2^n) moves — T(n) = 2T(n-1) + 1 = 2^n - 1
# space = O(n) auxiliary (the call stack); the `moves` list itself is O(2^n) output
def hanoi(n, src, dst, buf, moves):
    if n == 0:
        return
    hanoi(n - 1, src, buf, dst, moves)      # dst acts as the buffer here
    moves.append((src, dst))                # move the bottom disk
    hanoi(n - 1, buf, dst, src, moves)      # src acts as the buffer here

# hanoi(3, "A", "C", "B", moves)
#   -> A->C, A->B, C->B, A->C, B->A, B->C, A->C     (7 = 2^3 - 1 moves)

// java
// Towers of Hanoi - the same recursion on real stacks, so the invariant is checkable
// IDEA: recurse to park n-1 disks on the buffer, move one, recurse to restore them
// time = O(2^n), space = O(n)
void hanoi(int n, Deque<Integer> src, Deque<Integer> dst, Deque<Integer> buf) {
    if (n == 0) return;
    hanoi(n - 1, src, buf, dst);
    dst.push(src.pop());                    // smaller disks are all parked on buf
    hanoi(n - 1, buf, dst, src);
}

# python
# GENERAL PATTERN: all interleavings of two lists, each list's order preserved
# IDEA: take the head of one list, recurse, put it back; then the same for the other.
#       Mutate-recurse-restore keeps one copy of each list instead of slicing.
# time = O(C(m+n, m) * (m+n)) — one output per interleaving; space = O(m + n)
from collections import deque

def weave(first, second, prefix, out):
    if not first or not second:                  # one side is exhausted: no choice left
        out.append(prefix + list(first) + list(second))
        return

    head = first.popleft()                       # branch 1: take from `first`
    prefix.append(head)
    weave(first, second, prefix, out)
    prefix.pop()                                 # undo, exactly
    first.appendleft(head)

    head = second.popleft()                      # branch 2: take from `second`
    prefix.append(head)
    weave(first, second, prefix, out)
    prefix.pop()
    second.appendleft(head)

# python
# CtCI 4.9 - all insertion orders that rebuild this exact BST
# IDEA: root first, then weave every left-subtree order against every right-subtree
#       order — the two sides constrain each other in no way at all
# time = exponential in n (the answer itself is), space = O(n) per sequence
def all_sequences(node):
    if node is None:
        return [[]]                              # one empty order, not zero orders
    left = all_sequences(node.left)
    right = all_sequences(node.right)

    out = []
    for l in left:
        for r in right:
            weave(deque(l), deque(r), [node.val], out)
    return out

# BST     2          -> [[2, 1, 3], [2, 3, 1]]
#        / \
#       1   3