Backtracking
Subsets, permutations, partitions and constraint boards.
6 notes · 33 min total
Questions0 of 34 done
Warm up with these before Phase 1.
Patterns
- 1How to Design a Backtracking SolutionSix questions that turn a problem into a decision tree, how to estimate its cost from the input size, and why to construct, not filter.8 min
- 2Subsets, Combinations & Target SumsGenerate subsets and combinations with one start-index loop, skip duplicate siblings, and reach a target with or without reuse.6 min
- 3PermutationsBuild every ordering by trying each unused element at each position, skip duplicate siblings, and prune at placement time.4 min
- 4Partition into K BucketsSplit items into k equal groups by filling one bucket at a time, and prune with the stranded-number rule.5 min
- 5String PartitioningCut a string into valid pieces by growing a prefix one character at a time and recursing only when the prefix passes the rules.5 min
- 6Grid & Constraint BoardsBacktrack on grids by marking and unmarking cells, and solve boards like N-Queens and Sudoku with O(1) constraint sets.5 min