dsa2 min read
Combination Sum [Medium] — Backtracking with Pruning
Find all unique combinations that sum to a target, using backtracking with candidate reuse allowed.
Read →
Backtracking
33 articles
dsa2 min read
Permutations [Medium] — Backtracking via Swap
Generate all permutations of distinct integers using in-place swap backtracking.
Read →
dsa2 min read
Subsets [Medium] — Backtracking & Bit Manipulation
Generate the power set of distinct integers using backtracking or bitmask enumeration.
Read →
dsa2 min read
Combination Sum II [Medium] — Backtracking with Duplicate Skip
Find all unique combinations that sum to target where each number may be used once, skipping duplicates at each recursion level.
Read →
dsa2 min read
Word Search [Medium] — DFS Backtracking on Grid
Search for a word in a 2D grid using DFS backtracking with in-place visited marking.
Read →
dsa1 min read
Subsets II [Medium] — Backtracking with Duplicate Skip
Generate all unique subsets from an array with duplicates by sorting and skipping repeated elements at each recursion level.
Read →
dsa2 min read
Word Search — DFS with Backtracking
Search for a word in a grid by moving to adjacent cells without reuse. DFS with backtracking: mark visited, recurse, unmark.
Read →
dsa1 min read
All Paths Source to Target — DFS Backtracking
Find all paths from node 0 to node n-1 in a DAG. DFS with backtracking: explore each path, add to results when destination reached.
Read →
dsa1 min read
Word Ladder II — BFS Shortest Paths + DFS Reconstruct
Find ALL shortest transformation sequences. BFS builds layer map, DFS reconstructs all paths backwards from endWord to beginWord.
Read →
dsa1 min read
Path Sum II — DFS Backtracking All Paths
Collect all root-to-leaf paths with a given sum using DFS backtracking, appending and removing the current node.
Read →
dsa5 min read
Recursion & Backtracking Master Recap: Interview Cheatsheet
Complete backtracking reference: universal template, 7 pattern recognition cues, complexity guide, and top 30 interview problems.
Read →
dsa2 min read
Graph Coloring and Hamiltonian Path: Backtracking on Graphs
Color a graph with m colors (no adjacent same color) and find Hamiltonian paths using backtracking with neighbor constraint checking.
Read →
dsa3 min read
Remove Invalid Parentheses and Expression Parsing
Remove minimum invalid parentheses to produce all valid results. BFS approach for minimum removals, DFS for complete enumeration.
Read →
dsa3 min read
Beautiful Arrangement and Constraint Satisfaction
Solve Beautiful Arrangement and similar constraint-based permutation problems with backtracking and precomputed valid positions.
Read →
dsa3 min read
Subset Sum and Partition DP: Backtracking vs DP
Compare backtracking and DP approaches for subset sum: when to use each, conversion to knapsack, and bitset optimization.
Read →
dsa2 min read
Tiling and Splitting Problems: Backtracking meets DP
Solve tiling (domino, triomino) and optimal string splitting problems combining backtracking insight with DP optimization.
Read →
dsa2 min read
Knight's Tour and Maze Path Problems: Backtracking on Grids
Solve the Knight's Tour problem and maze path finding using backtracking with Warnsdorff heuristic for dramatic speedup.
Read →
dsa2 min read
Partition Problems: Equal Subset Sum and K Equal Parts
Solve partition backtracking problems: equal sum subset (NP-hard, backtrack with pruning) and k equal sum subsets.
Read →
dsa2 min read
Restore IP Addresses and Word Break II: Partition Backtracking
Generate valid IP addresses from digit strings and all sentence segmentations with word break backtracking.
Read →
dsa3 min read
Expression Add Operators: Backtracking with Precedence
Generate all expressions by inserting +, -, * between digits to reach target. Track running value and last operand for multiplication.
Read →
dsa2 min read
Palindrome Partitioning: Backtracking + DP Pre-check
Partition a string into all-palindrome substrings using backtracking with O(n^2) precomputed palindrome DP table for O(1) checks.
Read →
dsa2 min read
Letter Combinations of Phone Number: Backtracking
Generate all letter combinations from phone number digits using backtracking. Classic tree exploration with fixed branching factor.
Read →
dsa2 min read
Word Search I & II: DFS Backtracking on Grid
Search for words in a character grid using DFS backtracking. Word Search II uses a Trie for simultaneous multi-word search.
Read →
dsa2 min read
Generate Parentheses: Valid Combinations Backtracking
Generate all valid parentheses combinations of length 2n using open/close count tracking. Classic backtracking interview problem.
Read →
dsa3 min read
Sudoku Solver: Constraint Propagation + Backtracking
Solve a 9x9 Sudoku board with backtracking enhanced by constraint propagation (arc consistency) for dramatic pruning.
Read →
dsa3 min read
N-Queens: Classic Constraint Satisfaction Backtracking
Solve the N-Queens problem with backtracking using column/diagonal conflict tracking. O(n!) with early pruning.
Read →
dsa3 min read
Combinations and Combination Sum: Backtracking Variants
Generate all k-combinations and find combinations summing to target. Master the start-index pattern to avoid duplicates.
Read →
dsa2 min read
Generate All Permutations: Backtracking with Swap
Generate all n! permutations using backtracking with used[] array or in-place swap. Handles duplicates by sorting + skipping.
Read →
dsa2 min read
Generate All Subsets: Power Set with Backtracking
Generate all 2^n subsets of a set using backtracking (include/exclude) and bit masking. Handles duplicates with sorting + skip.
Read →
dsa2 min read
Recursion & Backtracking: Complete Guide
Master recursion and backtracking for DSA interviews: 7 core patterns, time complexity analysis, pruning strategies, and top 30 problems.
Read →
dsa2 min read
Word Search Problems — Trie + Backtracking Patterns
Word Search I and II solved with DFS backtracking. Word Search II uses a Trie to prune the search space from O(N·4^L) per word to O(N·4^L) total for all words.
Read →
dsa2 min read
Meta — Generate Parentheses (Backtracking)
Generate all combinations of well-formed parentheses of given n pairs using backtracking. Track open and close counts to prune invalid branches early.
Read →
dsa2 min read
Google — Word Break II (DP + Backtracking with Memoisation)
Return all ways to segment a string into dictionary words. Combines DP validity check with DFS+memo backtracking to avoid TLE on valid inputs.
Read →