Backtracking
Try a choice, keep going, and undo it if it fails, used to generate permutations, combinations, and valid layouts.
Backtracking Practice Problems
Medium
7 problems- 61medium
Subsets
Return every possible subset of a set of unique numbers.
- 62medium
Permutations
Return every possible ordering of a list of unique numbers.
- 63medium
Combination Sum
Find every combination of numbers from a list that adds up to a target, reusing numbers freely.
- 64medium
Letter Combinations of a Phone Number
Return every letter combination that a sequence of phone keypad digits could represent.
- 65medium
Palindrome Partitioning
Split a string into every possible way where each piece is a palindrome.
- 66medium
Generate Parentheses
Generate every combination of well-formed parentheses for a given number of pairs.
- 67medium
Word Search
Check whether a word can be traced through neighboring letters in a grid.
Hard
2 problemsRelated concepts
| Topic | Description |
|---|---|
| Recursion | Solve a problem by having a function call itself on a smaller version of the same problem until it hits a base case. |
| Depth-First Search | Explore as far as possible down one path before backtracking, used to walk trees, graphs, and grids. |
| Sliding Window | Solve fixed-window problems: maximum sum of k elements, moving averages, and O(n) updates as the window slides. |
| Two Pointers | Scan a sorted array or string from both ends at once to find pairs, remove duplicates, or reverse data in O(n). |
| Binary Search | Cut a sorted range in half on every step to find a value or boundary in O(log n) instead of checking one by one. |
| Breadth-First Search | Explore level by level from a starting point, the go-to way to find the shortest path in an unweighted graph. |