Recursion and backtracking are essential for solving problems where you need to explore all possibilities. Permutations, combinations, subsets, sudoku, and N-Queens all use backtracking. In this article, you will learn how recursion works, the backtracking template, and how to solve common interview problems.
We show core examples in Kotlin, Python, and Go.
What is Recursion?
Recursion is when a function calls itself. Every recursive function has two parts:
- Base case: the condition that stops recursion
- Recursive case: the function calls itself with a smaller problem
Python:
# Factorial: n! = n * (n-1) * ... * 1
def factorial(n):
if n <= 1: # Base case
return 1
return n * factorial(n - 1) # Recursive case
# factorial(4) = 4 * factorial(3)
# = 4 * 3 * factorial(2)
# = 4 * 3 * 2 * factorial(1)
# = 4 * 3 * 2 * 1 = 24
Kotlin:
fun factorial(n: Int): Int {
if (n <= 1) return 1
return n * factorial(n - 1)
}
Go:
func factorial(n int) int {
if n <= 1 {
return 1
}
return n * factorial(n-1)
}
How the Call Stack Works
Each recursive call adds a frame to the call stack. When the base case is reached, the stack unwinds.
factorial(4)
-> factorial(3)
-> factorial(2)
-> factorial(1) returns 1
returns 2 * 1 = 2
returns 3 * 2 = 6
returns 4 * 6 = 24
If you have n recursive calls, the stack depth is n, which means O(n) space. Too many calls cause a stack overflow.
Recursion vs Iteration
Any recursive solution can be rewritten as an iterative one. When should you use recursion?
| Use Recursion When | Use Iteration When |
|---|---|
| Tree/graph traversal | Simple loops |
| Backtracking problems | Performance-critical code |
| Divide and conquer | You want O(1) space |
| The recursive solution is much cleaner | Stack depth might be too large |
What is Backtracking?
Backtracking is recursion with a twist: you try an option, continue exploring, and if it does not work, you undo (backtrack) and try the next option.
Think of it like exploring a maze: you walk down a path, hit a dead end, go back to the last fork, and try a different path.
Backtracking Template
Python:
def backtrack(candidates, path, result):
if is_solution(path):
result.append(path[:]) # Save a copy of the current solution
return
for candidate in candidates:
if is_valid(candidate, path):
path.append(candidate) # Choose
backtrack(candidates, path, result) # Explore
path.pop() # Undo (backtrack)
The three steps are: Choose, Explore, Undo. This pattern solves almost every backtracking problem.
Subsets
Generate all subsets of a given set. For [1,2,3], the subsets are [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].
Python:
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # Every path is a valid subset
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
Kotlin:
fun subsets(nums: IntArray): List<List<Int>> {
val result = mutableListOf<List<Int>>()
fun backtrack(start: Int, path: MutableList<Int>) {
result.add(path.toList())
for (i in start until nums.size) {
path.add(nums[i])
backtrack(i + 1, path)
path.removeAt(path.size - 1)
}
}
backtrack(0, mutableListOf())
return result
}
Go:
func subsets(nums []int) [][]int {
result := [][]int{}
path := []int{}
var backtrack func(start int)
backtrack = func(start int) {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
return result
}
Time: O(n * 2^n). There are 2^n subsets, and copying each takes O(n). Space: O(n) for the recursion stack.
Permutations
Generate all permutations of a given array. For [1,2,3], the permutations are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].
Python:
def permutations(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
Kotlin:
fun permutations(nums: IntArray): List<List<Int>> {
val result = mutableListOf<List<Int>>()
val used = BooleanArray(nums.size)
fun backtrack(path: MutableList<Int>) {
if (path.size == nums.size) {
result.add(path.toList())
return
}
for (i in nums.indices) {
if (used[i]) continue
used[i] = true
path.add(nums[i])
backtrack(path)
path.removeAt(path.size - 1)
used[i] = false
}
}
backtrack(mutableListOf())
return result
}
Time: O(n * n!). There are n! permutations. Space: O(n).
Combination Sum
Find all unique combinations that sum to a target. Each number can be used multiple times.
Python:
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, not i+1 (reuse allowed)
path.pop()
backtrack(0, [], target)
return result
Go:
func combinationSum(candidates []int, target int) [][]int {
result := [][]int{}
path := []int{}
var backtrack func(start, remaining int)
backtrack = func(start, remaining int) {
if remaining == 0 {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
return
}
if remaining < 0 {
return
}
for i := start; i < len(candidates); i++ {
path = append(path, candidates[i])
backtrack(i, remaining-candidates[i])
path = path[:len(path)-1]
}
}
backtrack(0, target)
return result
}
N-Queens
Place n queens on an n x n chessboard so that no two queens attack each other.
Python:
def solve_n_queens(n):
result = []
board = [["."] * n for _ in range(n)]
def is_valid(row, col):
# Check column
for i in range(row):
if board[i][col] == "Q":
return False
# Check upper-left diagonal
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == "Q":
return False
i -= 1
j -= 1
# Check upper-right diagonal
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == "Q":
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
result.append(["".join(r) for r in board])
return
for col in range(n):
if is_valid(row, col):
board[row][col] = "Q" # Choose
backtrack(row + 1) # Explore
board[row][col] = "." # Undo
backtrack(0)
return result
Kotlin:
fun solveNQueens(n: Int): List<List<String>> {
val result = mutableListOf<List<String>>()
val board = Array(n) { CharArray(n) { '.' } }
fun isValid(row: Int, col: Int): Boolean {
for (i in 0 until row) {
if (board[i][col] == 'Q') return false
}
var i = row - 1; var j = col - 1
while (i >= 0 && j >= 0) {
if (board[i][j] == 'Q') return false
i--; j--
}
i = row - 1; j = col + 1
while (i >= 0 && j < n) {
if (board[i][j] == 'Q') return false
i--; j++
}
return true
}
fun backtrack(row: Int) {
if (row == n) {
result.add(board.map { String(it) })
return
}
for (col in 0 until n) {
if (isValid(row, col)) {
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
}
}
}
backtrack(0)
return result
}
Time: O(n!). Space: O(n^2) for the board.
Pruning: Making Backtracking Faster
Pruning means skipping paths that cannot lead to a valid solution. This can dramatically reduce the number of paths explored.
Example: Skip duplicates in subsets
def subsets_with_dup(nums):
nums.sort() # Sort to group duplicates
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # Prune: skip duplicate at this level
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
Example: Sort candidates in combination sum for early termination
def combination_sum_pruned(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # Prune: all remaining candidates are too large
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return result
Recursion with Memoization (Preview)
When recursive calls repeat the same subproblems, add memoization to cache results. This is the foundation of dynamic programming, which we cover in the next article.
Python:
# Without memoization: O(2^n)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# With memoization: O(n)
def fibonacci_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
Common Mistakes
Forgetting the base case. Without a base case, recursion runs forever (stack overflow).
Not making a copy when saving results.
result.append(path)saves a reference, not a copy. The path will change later. Useresult.append(path[:])in Python orpath.toList()in Kotlin.Modifying global state without undoing it. Every “choose” must have a matching “undo.” If you mark a cell as visited, unmark it after backtracking.
Not pruning when possible. Sorting candidates and breaking early can reduce runtime from seconds to milliseconds.
Practice Problems
| Problem | Type | LeetCode # |
|---|---|---|
| Subsets | Backtracking | #78 |
| Subsets II (with duplicates) | Backtracking + pruning | #90 |
| Permutations | Backtracking | #46 |
| Combination Sum | Backtracking | #39 |
| Combination Sum II | Backtracking + pruning | #40 |
| N-Queens | Backtracking | #51 |
| Word Search | Backtracking on grid | #79 |
| Palindrome Partitioning | Backtracking | #131 |
What’s Next?
Recursion with memoization leads directly to dynamic programming. In the next article, you will learn Dynamic Programming — how to solve optimization problems by breaking them into overlapping subproblems.
Next: DSA Tutorial #16: Dynamic Programming
Full series: DSA from Zero to Interview Ready