Part IV · Fundamental Algorithm Design Paradigms
20. Backtracking, Constraint Search and State Space
7 lessons•37 topics•Intermediate
7 of 7 lessons published
20.015 animated
Backtracking method
- Decision tree
- Choose-explore-unchoose
- Partial solution
- Undo changes
- Pruning
- Validity checks
20.025 animated
Subset and permutation generation
- Subsets
- Power set
- Subsequences
- All permutations
- Unique permutations with duplicates
- Combinations
20.036 animated
Constraint problems
- N-Queens
- Sudoku solver
- Word search
- Rat in a maze
- Graph coloring
- Hamiltonian path basic search
20.045 animated
Partitioning and sum problems
- Combination sum
- Subset sum enumeration
- Equal-sum partitions
- K-partition
- Matchsticks to square
20.055 animated
String backtracking
- Generate parentheses
- Palindrome partitioning
- Letter combinations
- Restore IP addresses
- Word break enumeration
20.065 animated
Search improvements
- Ordering choices
- Branch and bound
- Symmetry breaking
- Constraint propagation
- Heuristic variable selection
20.072 animated
Exact cover introduction
- Exact cover formulation
- Algorithm X
- Dancing Links overview
- Sudoku exact cover