DSA/Backtracking

Backtracking

This is a premium interview-preparation course built around one template that solves a whole family of problems: **choose, explore, unchoose**. Backtracking is depth-first search over a decision tree — at each node you make a choice, recurse to explore its consequences, then undo the choice so the next branch starts clean. The art is not the recursion itself but knowing **what a state is**, **how choices branch**, and **when to prune** so an exponential space stays tractable. You will start with the mental model (decision trees, state-space search, the recursion tree, and how to reason about complexity), then work through curated problems grouped by the patterns interviewers actually test: subsets, permutations, combinations, string partitioning, board search, and advanced pruning. Every lesson recognises the pattern first, draws the recursion tree, explains the pruning, then shows a clean Java 17 implementation.

Curated lessons

Learning modules

7h 14m

Est. study time

Target companies

What you'll learn

Recognise the backtracking signal: build every valid configuration by making and undoing sequential choices.
Model state, choices, and the base case so the choose/explore/unchoose template writes itself.
Prune aggressively — sort-and-skip duplicates, bound checks, and early termination — to tame the search tree.
Reason about the size of the decision tree to state honest time and space complexity.

Your progress

0 / 25

problems completed

25 available now · keep going!

Mark lessons complete as you work through them. Progress is saved on this device and syncs to your account when you sign in.

Learning roadmap

Work top to bottom — each module builds on the last.

1
Backtracking Fundamentals
DFS over choices: choose, explore, unchoose
The mental model: a decision tree over a state space, the choose/explore/unchoose template, pruning, and how to reason about the recursion tree's size.
8/8 problems1h 1m
2
Subset Pattern
Take / skip each index; sort-skip duplicates
Include-or-exclude each element to enumerate the power set, then learn the sort-and-skip trick that removes duplicate subsets.
2/2 problems34m
3
Permutation Pattern
Fix each position with an unused element
Order matters: place every unused element at each position, and prune duplicate permutations with a used-array plus sorted skip.
2/2 problems38m
4
Combination Pattern
Start-index recursion; bound and skip
Choose k of n without regard to order using a start index, then add target sums, reuse rules, and duplicate skipping.
4/4 problems1h 16m
5
String Backtracking
Choose a prefix / cut point, recurse on the rest
Partition and map strings: expand phone digits, cut a string into palindromes, and place dots to form valid IP addresses.
3/3 problems58m
6
Board Search
Place, validate, recurse, undo the cell
Search a grid with constraints: walk a word through a matrix, place non-attacking queens, and solve Sudoku with constraint propagation.
3/3 problems1h 25m
7
Advanced Backtracking
Aggressive pruning over a wide decision tree
Harder search spaces where pruning is the whole game: inject operators between digits, fill buckets to equal sums, and split into descending values.
3/3 problems1h 22m

Modules

7 themed modules from fundamentals to advanced.

Backtracking Fundamentals

The mental model: a decision tree over a state space, the choose/explore/unchoose template, pruning, and how to reason about the recursion tree's size.

8/8 problems1h 1m

Subset Pattern

Include-or-exclude each element to enumerate the power set, then learn the sort-and-skip trick that removes duplicate subsets.

2/2 problems34m

Permutation Pattern

Order matters: place every unused element at each position, and prune duplicate permutations with a used-array plus sorted skip.

2/2 problems38m

Combination Pattern

Choose k of n without regard to order using a start index, then add target sums, reuse rules, and duplicate skipping.

4/4 problems1h 16m

String Backtracking

Partition and map strings: expand phone digits, cut a string into palindromes, and place dots to form valid IP addresses.

3/3 problems58m

Board Search

Search a grid with constraints: walk a word through a matrix, place non-attacking queens, and solve Sudoku with constraint propagation.

3/3 problems1h 25m

Advanced Backtracking

Harder search spaces where pruning is the whole game: inject operators between digits, fill buckets to equal sums, and split into descending values.

3/3 problems1h 22m

Full curriculum

17 problems and 8 concept lessons in learning order.

Techniques you'll master

AnalysisArrayBacktrackingBoard SearchCombinationsComplexityConstraint PropagationConstraint TrackingDFSDecision TreeDuplicate HandlingDuplicate SkippingDuplicatesExpression EvaluationFoundationsIn-place MarkingInterviewsJavaMappingMatrixNumber ParsingOptimizationPalindromePartitioningPattern RecognitionPermutationPower SetPruningRecursionRecursion TreeSortingState SpaceStringSubset PatternTemplate