Recursion & Backtracking

IntermediateAlgorithms

Backtracking systematically explores all possibilities by building candidates incrementally and abandoning (pruning) paths that cannot lead to a solution. Essential for permutations, subsets, and constraint satisfaction.

AVG TIME

O(2^n)

SPACE

O(n)

BEST

O(n!)

WORST

O(n!)

Key Concepts

1Backtracking template: choose, explore, unchoose
2Subsets: at each element, decide to include or exclude
3Permutations: swap elements with remaining positions
4Pruning early is critical for performance
5State must be fully restored after each recursive call

In Python

Concept to Code- 2 structures for this topic

declare

nums = [1, 2, 3]

common ops

nums.append(x)

O(1)

nums.pop()

O(1)

nums[i]

O(1)

nums.insert(i, x)

O(n)

x in nums

O(n)

nums.sort()

O(n log n)

len(nums)

O(1)

say in interview

"I'll use an array to store the elements"

Python lists ARE dynamic arrays (like ArrayList in Java), NOT linked lists. Access by index is O(1).

Math You Need For This

A maze where you try every path. When you hit a dead end you backtrack to the last fork and try a different direction. Stack space = how deep you are in the maze, not the total number of paths.

Required concepts

Key math ideas

1 / 3

Recursion - functions that call themselves

A recursive function solves a big problem by solving a slightly smaller version of the same problem, and keeps going until it hits a base case small enough to answer directly. Think of it as Russian nesting dolls - each doll contains a smaller version of itself, until you reach the tiny solid doll at the center.

Call stack (top = most recent):

factorial(4)

waiting for factorial(3)

1/7

Think of it this way: To find the total weight of a stack of boxes, you pick up the top box, weigh it, then ask someone to tell you the total weight of the remaining stack. They do the same thing. Eventually the last person just says "zero, there are no boxes left."

For algorithms: Trees, graphs, and divide-and-conquer algorithms are all inherently recursive. Once recursion clicks, these topics open up.

Interactive 3D Visualization

Binary Tree (BST)
Search: O(log n)Insert: O(log n)Space: O(n)
Drag to orbit  -  Scroll to zoom

Python Implementation

example.py

Now try it yourself

1 challenge with test cases and AI feedback

Practice Now

Complexity Analysis

COMMON OPERATIONS

Array

Access:O(1)

Search:O(n)

Insert end:O(1)*

Insert mid:O(n)

Hash Map

Get/Set:O(1)*

Delete:O(1)*

Search value:O(n)

Iterate:O(n)

Linked List

Access:O(n)

Search:O(n)

Insert head:O(1)

Delete known:O(1)

Binary Search

Search:O(log n)

Insert:O(log n)

Balanced BST

Search:O(log n)

Insert:O(log n)

Delete:O(log n)

Heap

Peek min/max:O(1)

Push:O(log n)

Pop:O(log n)

Heapify:O(n)

Graph (BFS/DFS)

Traversal:O(V+E)

Dijkstra (heap):O((V+E) log V)

Merge / Quick Sort

Sort:O(n log n)

Space (merge):O(n)

Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Recursion & Backtracking into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Dynamic Programming

Recursion & Backtracking

Next: Dynamic Programming