Recursion & Backtracking — The Complete Visual Reference

fun solve(problem: Problem): Result { // 1. Base case — smallest subproblem if (problem.isSimple()) return trivialAnswer // 2. Recursive case — break down val sub = solve(problem.smaller()) // 3. Combine — build answer return combine(problem, sub) }

// Sum of array — traced step by step fun sum(arr: IntArray, i: Int = 0): Int { if (i == arr.size) return 0 // base return arr[i] + sum(arr, i + 1) // recurse + combine } // sum([3,1,4]) → 3 + sum([1,4]) → 3 + 1 + sum([4]) → 3 + 1 + 4 + 0 = 8

// Recursive fun factRec(n: Int): Long = if (n <= 1) 1 else n * factRec(n - 1) // Iterative fun factIter(n: Int): Long { var result = 1L for (i in 2..n) result *= i return result }

// NON-tail: multiplication happens AFTER recursive call fun fact(n: Int): Long = if (n <= 1) 1 else n * fact(n - 1) // × after call! // TAIL: recursive call IS the last operation tailrec fun factTR(n: Int, acc: Long = 1): Long = if (n <= 1) acc else factTR(n - 1, n * acc)

// Kotlin tailrec examples — compile to loops! tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) tailrec fun sumTR(arr: IntArray, i: Int = 0, acc: Int = 0): Int = if (i == arr.size) acc else sumTR(arr, i + 1, acc + arr[i]) tailrec fun binSearch( arr: IntArray, t: Int, lo: Int = 0, hi: Int = arr.size - 1 ): Int { if (lo > hi) return -1 val mid = (lo + hi) / 2 return when { arr[mid] == t -> mid arr[mid] < t -> binSearch(arr, t, mid + 1, hi) else -> binSearch(arr, t, lo, mid - 1) } }

// Factorial — O(n) fun factorial(n: Int): Long = if (n <= 1) 1 else n * factorial(n - 1) // Fibonacci naive — O(2^n) TIME! fun fibNaive(n: Int): Int = if (n <= 1) n else fibNaive(n - 1) + fibNaive(n - 2) // Fibonacci memoized — O(n) fun fibMemo(n: Int, memo: MutableMap<Int, Int> = mutableMapOf()): Int = memo.getOrPut(n) { if (n <= 1) n else fibMemo(n - 1, memo) + fibMemo(n - 2, memo) } // Fibonacci tail-recursive — O(1) space tailrec fun fibTR(n: Int, a: Int = 0, b: Int = 1): Int = if (n == 0) a else fibTR(n - 1, b, a + b)

// Fast Power — O(log n) binary exponentiation fun fastPow(base: Long, exp: Int, mod: Long = 1_000_000_007): Long { if (exp == 0) return 1 val half = fastPow(base, exp / 2, mod) return if (exp % 2 == 0) half * half % mod else half * half % mod * base % mod }

fun reverseString(s: String): String = if (s.isEmpty()) s else reverseString(s.substring(1)) + s[0] fun isPalindrome(s: String, l: Int = 0, r: Int = s.lastIndex): Boolean = l >= r || (s[l] == s[r] && isPalindrome(s, l + 1, r - 1)) // Generate all subsequences — O(2^n) fun subsequences(s: String, i: Int = 0, cur: String = ""): List<String> { if (i == s.length) return listOf(cur) return subsequences(s, i + 1, cur) + // exclude subsequences(s, i + 1, cur + s[i]) // include }

fun reverseList(head: ListNode?): ListNode? { if (head?.next == null) return head val newHead = reverseList(head.next) head.next!!.next = head head.next = null return newHead } fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? { if (l1 == null) return l2 if (l2 == null) return l1 return if (l1.`val` <= l2.`val`) { l1.next = mergeTwoLists(l1.next, l2); l1 } else { l2.next = mergeTwoLists(l1, l2.next); l2 } } fun removeElements(head: ListNode?, v: Int): ListNode? { if (head == null) return null head.next = removeElements(head.next, v) return if (head.`val` == v) head.next else head }

fun maxDepth(root: TreeNode?): Int = if (root == null) 0 else 1 + maxOf(maxDepth(root.left), maxDepth(root.right)) fun countNodes(root: TreeNode?): Int = if (root == null) 0 else 1 + countNodes(root.left) + countNodes(root.right) fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean = (p == null && q == null) || (p != null && q != null && p.`val` == q.`val` && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) fun lca(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? { if (root == null || root == p || root == q) return root val left = lca(root.left, p, q) val right = lca(root.right, p, q) return if (left != null && right != null) root else left ?: right }

// Merge Sort — canonical D&C fun mergeSort(arr: IntArray): IntArray { if (arr.size <= 1) return arr val mid = arr.size / 2 val left = mergeSort(arr.sliceArray(0 until mid)) val right = mergeSort(arr.sliceArray(mid until arr.size)) return merge(left, right) } // Count Inversions — merge sort variant fun countInversions(arr: IntArray): Long { if (arr.size <= 1) return 0 val mid = arr.size / 2 val left = arr.sliceArray(0 until mid) val right = arr.sliceArray(mid until arr.size) var count = countInversions(left) + countInversions(right) // count split inversions during merge var i = 0; var j = 0 for (k in arr.indices) { if (j >= right.size || (i < left.size && left[i] <= right[j])) arr[k] = left[i++] else { arr[k] = right[j++]; count += left.size - i } } return count }

// Memoization template fun solve(state: State, memo: MutableMap<State, Result>): Result { memo[state]?.let { return it } // 1. check cache if (isBase(state)) return baseVal // 2. base case val result = /* recurse */ // 3. recurse memo[state] = result // 4. cache result return result }

// Fibonacci with memo fun fib(n: Int, m: MutableMap<Int,Int> = mutableMapOf()): Int = m.getOrPut(n) { if (n <= 1) n else fib(n-1,m) + fib(n-2,m) } // Climb Stairs — ways to climb n steps (1 or 2 at a time) fun climbStairs(n: Int, m: MutableMap<Int,Int> = mutableMapOf()): Int = m.getOrPut(n) { if (n <= 1) 1 else climbStairs(n-1,m) + climbStairs(n-2,m) } // Coin Change — min coins to make amount fun coinChange(coins: IntArray, amt: Int, m: MutableMap<Int,Int> = mutableMapOf()): Int = m.getOrPut(amt) { if (amt == 0) 0 else if (amt < 0) Int.MAX_VALUE else coins.minOf { coinChange(coins, amt - it, m) } .let { if (it == Int.MAX_VALUE) it else it + 1 } } // LCS — Longest Common Subsequence fun lcs(a: String, b: String, i: Int = 0, j: Int = 0, m: MutableMap<Pair<Int,Int>,Int> = mutableMapOf()): Int = m.getOrPut(i to j) { if (i == a.length || j == b.length) 0 else if (a[i] == b[j]) 1 + lcs(a, b, i+1, j+1, m) else maxOf(lcs(a, b, i+1, j, m), lcs(a, b, i, j+1, m)) }

// Template 1 — Collect ALL solutions fun backtrack(state: State, choices: List, result: MutableList<List>) { if (isGoal(state)) { result.add(state.toList()); return } for (choice in choices) { if (!isValid(choice)) continue // prune state.add(choice) // choose backtrack(state, nextChoices) // explore state.removeLast() // unchoose } }

// Template 2 — Find ANY solution (return true/false) fun backtrack(state: State): Boolean { if (isGoal(state)) return true for (choice in choices) { if (!isValid(choice)) continue state.add(choice) if (backtrack(state)) return true // found! state.removeLast() } return false // no solution }

// Template 3 — Count solutions fun backtrack(state: State): Int { if (isGoal(state)) return 1 var count = 0 for (choice in choices) { if (!isValid(choice)) continue state.add(choice) count += backtrack(state) state.removeLast() } return count }

// Template 4 — Optimize (find best, prune with bound) var best = Int.MAX_VALUE fun backtrack(state: State, cost: Int) { if (cost >= best) return // prune — can't beat best if (isGoal(state)) { best = cost; return } for (choice in choices) { if (!isValid(choice)) continue state.add(choice) backtrack(state, cost + choice.cost) state.removeLast() } }

// All subsets fun subsets(nums: IntArray): List<List<Int>> { val result = mutableListOf<List<Int>>() fun bt(start: Int, cur: MutableList<Int>) { result.add(cur.toList()) // record at every node for (i in start until nums.size) { cur.add(nums[i]) bt(i + 1, cur) cur.removeLast() } } bt(0, mutableListOf()) return result } // Subsets with duplicates — sort + skip fun subsetsWithDup(nums: IntArray): List<List<Int>> { nums.sort() val result = mutableListOf<List<Int>>() fun bt(start: Int, cur: MutableList<Int>) { result.add(cur.toList()) for (i in start until nums.size) { if (i > start && nums[i] == nums[i-1]) continue // skip dup cur.add(nums[i]); bt(i + 1, cur); cur.removeLast() } } bt(0, mutableListOf()) return result } // Bitmask alternative fun subsetsBitmask(nums: IntArray): List<List<Int>> = (0 until (1 shl nums.size)).map { mask -> nums.filterIndexed { i, _ -> mask and (1 shl i) != 0 } }

// All permutations — loop from 0 with used[] fun permutations(nums: IntArray): List<List<Int>> { val result = mutableListOf<List<Int>>() val used = BooleanArray(nums.size) fun bt(cur: MutableList<Int>) { if (cur.size == nums.size) { result.add(cur.toList()); return } for (i in nums.indices) { if (used[i]) continue used[i] = true; cur.add(nums[i]) bt(cur) cur.removeLast(); used[i] = false } } bt(mutableListOf()) return result } // Permutations with duplicates — sort + skip fun permuteUnique(nums: IntArray): List<List<Int>> { nums.sort() val result = mutableListOf<List<Int>>() val used = BooleanArray(nums.size) fun bt(cur: MutableList<Int>) { if (cur.size == nums.size) { result.add(cur.toList()); return } for (i in nums.indices) { if (used[i]) continue if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue used[i] = true; cur.add(nums[i]) bt(cur) cur.removeLast(); used[i] = false } } bt(mutableListOf()) return result }

// C(n, k) — choose k from 1..n fun combine(n: Int, k: Int): List<List<Int>> { val result = mutableListOf<List<Int>>() fun bt(start: Int, cur: MutableList<Int>) { if (cur.size == k) { result.add(cur.toList()); return } for (i in start..n) { cur.add(i); bt(i + 1, cur); cur.removeLast() } } bt(1, mutableListOf()) return result } // Combination Sum — reuse allowed (use i, not i+1) fun combinationSum(cands: IntArray, target: Int): List<List<Int>> { val result = mutableListOf<List<Int>>() fun bt(start: Int, rem: Int, cur: MutableList<Int>) { if (rem == 0) { result.add(cur.toList()); return } for (i in start until cands.size) { if (cands[i] > rem) break // prune cur.add(cands[i]) bt(i, rem - cands[i], cur) // i, not i+1 → reuse cur.removeLast() } } cands.sort() bt(0, target, mutableListOf()) return result } // Combination Sum 2 — no reuse, skip duplicates fun combinationSum2(cands: IntArray, target: Int): List<List<Int>> { cands.sort() val result = mutableListOf<List<Int>>() fun bt(start: Int, rem: Int, cur: MutableList<Int>) { if (rem == 0) { result.add(cur.toList()); return } for (i in start until cands.size) { if (cands[i] > rem) break if (i > start && cands[i] == cands[i-1]) continue cur.add(cands[i]) bt(i + 1, rem - cands[i], cur) // i+1 → no reuse cur.removeLast() } } bt(0, target, mutableListOf()) return result }

fun generateParenthesis(n: Int): List<String> { val result = mutableListOf<String>() fun bt(cur: StringBuilder, open: Int, close: Int) { if (cur.length == 2 * n) { result.add(cur.toString()); return } if (open < n) { cur.append('(') bt(cur, open + 1, close) cur.deleteCharAt(cur.lastIndex) } if (close < open) { cur.append(')') bt(cur, open, close + 1) cur.deleteCharAt(cur.lastIndex) } } bt(StringBuilder(), 0, 0) return result }

fun solveNQueens(n: Int): List<List<String>> { val result = mutableListOf<List<String>>() val cols = mutableSetOf<Int>() val diag1 = mutableSetOf<Int>() // row - col val diag2 = mutableSetOf<Int>() // row + col val board = IntArray(n) { -1 } // board[row] = col fun bt(row: Int) { if (row == n) { result.add(board.map { col -> ".".repeat(col) + "Q" + ".".repeat(n - col - 1) }) return } for (col in 0 until n) { if (col in cols || row-col in diag1 || row+col in diag2) continue board[row] = col cols.add(col); diag1.add(row-col); diag2.add(row+col) bt(row + 1) cols.remove(col); diag1.remove(row-col); diag2.remove(row+col) } } bt(0) return result }

fun solveSudoku(board: Array<CharArray>): Boolean { for (r in 0..8) for (c in 0..8) { if (board[r][c] != '.') continue for (d in '1'..'9') { if (isValidPlacement(board, r, c, d)) { board[r][c] = d if (solveSudoku(board)) return true board[r][c] = '.' // backtrack } } return false // no digit works } return true // all filled } fun isValidPlacement(b: Array<CharArray>, r: Int, c: Int, d: Char): Boolean { for (i in 0..8) { if (b[r][i] == d) return false // row if (b[i][c] == d) return false // col if (b[r/3*3+i/3][c/3*3+i%3] == d) return false // box } return true }

fun exist(board: Array<CharArray>, word: String): Boolean { val m = board.size; val n = board[0].size val dirs = intArrayOf(0,1,0,-1,0) fun dfs(r: Int, c: Int, k: Int): Boolean { if (k == word.length) return true if (r !in 0 until m || c !in 0 until n) return false if (board[r][c] != word[k]) return false val tmp = board[r][c] board[r][c] = '#' // mark visited for (d in 0..3) { if (dfs(r + dirs[d], c + dirs[d+1], k + 1)) return true } board[r][c] = tmp // RESTORE — backtrack return false } for (r in 0 until m) for (c in 0 until n) if (dfs(r, c, 0)) return true return false }

fun palindromePartition(s: String): List<List<String>> { val result = mutableListOf<List<String>>() fun isPalin(l: Int, r: Int): Boolean { var i = l; var j = r while (i < j) { if (s[i++] != s[j--]) return false } return true } fun bt(start: Int, cur: MutableList<String>) { if (start == s.length) { result.add(cur.toList()); return } for (end in start until s.length) { if (isPalin(start, end)) { cur.add(s.substring(start, end + 1)) bt(end + 1, cur) cur.removeLast() } } } bt(0, mutableListOf()) return result }

fun addOperators(num: String, target: Long): List<String> { val result = mutableListOf<String>() fun bt(i: Int, expr: String, eval: Long, last: Long) { if (i == num.length) { if (eval == target) result.add(expr) return } for (j in i until num.length) { if (j > i && num[i] == '0') break // no leading zeros val cur = num.substring(i, j + 1).toLong() if (i == 0) { bt(j + 1, "$cur", cur, cur) } else { bt(j+1, "$expr+$cur", eval + cur, cur) bt(j+1, "$expr-$cur", eval - cur, -cur) // * precedence: undo last, apply multiply bt(j+1, "$expr*$cur", eval - last + last * cur, last * cur) } } } bt(0, "", 0, 0) return result }

fun restoreIpAddresses(s: String): List<String> { val result = mutableListOf<String>() fun bt(start: Int, parts: MutableList<String>) { if (parts.size == 4) { if (start == s.length) result.add(parts.joinToString(".")) return } for (len in 1..3) { if (start + len > s.length) break val part = s.substring(start, start + len) if (part.length > 1 && part[0] == '0') continue // no leading 0 if (part.toInt() > 255) continue parts.add(part) bt(start + len, parts) parts.removeLast() } } bt(0, mutableListOf()) return result }

// 1. Constraint propagation — check validity BEFORE recursing if (col in cols || diag1 in d1 || diag2 in d2) continue // 2. Sort for early termination cands.sort() if (cands[i] > remaining) break // all remaining too large // 3. Skip duplicates at same decision level if (i > start && nums[i] == nums[i-1]) continue // 4. Symmetry breaking — only explore first option if (row == 0 && col > n / 2) break // N-Queens: half of first row // 5. Bound-based pruning — can't beat current best if (cost + lowerBound(remaining) >= best) return // 6. Memoization — cache repeated subproblems memo[state]?.let { return it } // 7. Most-constrained variable — fill hardest cell first val cell = emptyCells.minByOrNull { it.numOptions }

// BUG 1: Missing base case → infinite recursion fun bad(n: Int): Int = n * bad(n - 1) // never stops! fun good(n: Int): Int = if (n <= 1) 1 else n * good(n - 1) // BUG 2: Incomplete base cases fun bad(n: Int): Int = if (n == 0) 1 else n * bad(n - 1) // fails for negative! // BUG 3: Forgetting to backtrack (undo choice) cur.add(nums[i]) bt(i + 1, cur) // cur.removeLast() ← MISSING! State leaks to next iteration // BUG 4: Adding reference instead of copy result.add(current) // BAD — same list mutated later result.add(current.toList()) // GOOD — snapshot copy // BUG 5: Not sorting before duplicate skip // nums = [1, 2, 1] → skip logic FAILS without sort nums.sort() // [1, 1, 2] → now skip works if (i > start && nums[i] == nums[i-1]) continue // BUG 6: Exponential time from missing memoization fun fib(n: Int): Int = if (n <= 1) n else fib(n-1) + fib(n-2) // O(2^n)! // BUG 7: Wrong start index // i+1 → no reuse (subsets, combSum2) // i → reuse allowed (combSum) // 0 → permutations (with used[]) // BUG 8: Mutating global state without restoring visited[r][c] = true dfs(r + 1, c) // visited[r][c] = false ← MISSING! Blocks other paths