Pruning [mp]
Micro pattern¶
Description¶
Stop exploring a branch when an invariant proves it cannot yield a new valid result.
Problems¶
Reject invalid prefixes¶
Recurse only while the partial result remains completable.
- 22. Generate Parentheses (Top Medium)
- 131. Palindrome Partitioning (Top Hard)
- 301. Remove Invalid Parentheses (Top Hard)
Discard an ordered subtree¶
Skip a complete subtree using an ordering invariant.
- 669. Trim a Binary Search Tree (Google Prep)
Remove exhausted search branches¶
Delete search branches that can no longer emit a result.
- 212. Word Search II (Top Hard)
Ignore nonbeneficial contributions¶
Clamp a contribution that would worsen every extension.
- 124. Binary Tree Maximum Path Sum (Top Hard)
Bound candidate lengths¶
Consider only substring lengths present in the dictionary.
- 139. Word Break (Top Hard)
- 140. Word Break II (Top Hard)
Reject impossible moves¶
Skip transitions barred by current state or known constraints.
- 864. Shortest Path to Get All Keys (Graph Theory)