4 patterns · 18 problems
Recursion
Solve a problem in terms of smaller versions of itself: divide & conquer, backtracking, and recursive search.
Each pattern below starts with when to reach for it and the clue in the prompt that gives it away. Then it runs on real problems: pick one to watch the technique step by step, open its full solution, or practise it on an original problem with graded tests.
01Pattern
Basic Recursive Functions
Call yourself on a smaller problem until you hit bottom.
When to reach for it
- Implement basic recursive functions that solve a problem by dividing it into smaller instances of the same problem until a base case is reached.
Spot it in the prompt
Problems where the solution can be naturally expressed in terms of smaller instances of the same problem, such as factorial calculation, Fibonacci sequence generation, or exponentiation.
N-th Tribonacci Number
How to solve it
Animation shows the Basic Recursive Functions techniqueDefine T(n) = T(n-1) + T(n-2) + T(n-3) recursively from the base cases, memoizing so shared subproblems aren't recomputed.
Three-Day Dispatch Ladder is our own problem on the same technique: a new statement, graded in your browser.
02Pattern
Divide & Conquer
Split, solve each half, then merge the answers.
O(n log n)naïve O(n²)When to reach for it
- Break down a problem into smaller subproblems of the same type, solve each subproblem recursively, and combine their solutions to solve the original problem.
Spot it in the prompt
Tasks where the solution to a larger problem can be obtained by recursively combining solutions to smaller instances of the same problem, such as binary search or finding maximum or minimum elements in an array.
Binary Search
How to solve it
Recurse on half the sorted array by comparing the middle element to the target, discarding the impossible half each call.
Survey Marker Lookup is our own problem on the same technique: a new statement, graded in your browser.
03Pattern
Backtracking
Try a choice, recurse, undo it, try the next.
When to reach for it
- Explore all potential solutions to a problem by trying out different choices and backtracking when a dead-end is reached, undoing choices and trying alternative paths.
Spot it in the prompt
Problems where you need to find all permutations, combinations, or subsets of elements while satisfying specific constraints.
Generate Parentheses
How to solve it
Animation shows the Backtracking techniqueRecursively add '(' while open < n and ')' while close < open, recording each complete valid string.
Ridge Walk Plans is our own problem on the same technique: a new statement, graded in your browser.
04Pattern
Recursive Search
Explore branches recursively until you find the target.
When to reach for it
- Search for a target element or solution recursively by exploring different branches of a search space until the target is found or the search space is exhausted.
Spot it in the prompt
Problems involving searching for specific elements or solutions in a structured or unstructured search space. Tasks requiring finding paths in mazes, solving Sudoku puzzles, or searching for elements in a tree or graph.
Number of Islands
How to solve it
Scan the grid and flood-fill via DFS from each unvisited land cell, sinking connected land and counting one island per launch.
After the pattern
Now solve one you haven't seen.
Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.
1,194 problems · 15,062 graded tests · free