Generating combinations, permutations and valid configurations.
- all combinations
- choose or skip
- return every valid arrangement
The current path represents exactly the decisions made before the current depth.
Often exponential because the output is exponential. Typical auxiliary space: O(depth), excluding output.
JAVA STARTING POINT
A template to adapt, not memorize.
path.add(value);
search(nextIndex, path, answer);
path.remove(path.size() - 1);
search(nextIndex, path, answer);Common mistakes
- Forgetting to undo a choice
- Adding the mutable path without copying it
- Claiming output space as constant
PUBLISHED / 29
Learn in this order.
Available articles always appear before the publishing plan.
Subsets in Java: From Brute Force to Optimal
Generate every subset of a distinct integer set in Java using bitmasks and backtracking, with a visual dry run and honest complexity analysis.
Read article →Subsets I in Java: Find Every Subset Sum
Understand take-or-skip recursion by producing every subset sum, with repeated sums, commented Java, a recursion tree and a dry run.
Read article →Combination Sum in Java: Why Taking Keeps the Same Index
Build reusable-candidate combinations with take/skip recursion, understand the remaining target and undo steps, and analyze output-sensitive complexity.
Read article →Combination Sum II in Java: Use Each Index Once, Skip Duplicate Branches
Understand i+1, sorted candidate pruning and sibling duplicate skipping with repeated values, a worked target-sum example and commented Java.
Read article →Subsets II in Java: Unique Subsets Without Losing Repeated Values
Generate unique subsets with duplicates using sorted sibling choices, preserve repeated values inside subsets, and understand copying and undo.
Read article →Generate Parentheses in Java: Keep Every Prefix Balanced
Build balanced parentheses using remaining counts, understand why close must exceed open, and trace the valid prefix tree.
Read article →Permutations of a String in Java: Swap, Restore and Remove Duplicates
Generate sorted unique string permutations using your swap-and-backtrack approach, with per-position duplicate handling and an honest sorting cost.
Read article →Brace Expansion in Java: Parse Choices, Then Build Words
Turn flat brace expressions into sorted choice groups, generate their Cartesian product with recursion, and distinguish nested Brace Expansion II.
Read article →Word Pattern II in Java: Backtrack a Two-Way Mapping
Understand bijection, two string indices, candidate substrings, successful short-circuiting and undo with a beginner-friendly Word Pattern II solution.
Read article →Strobogrammatic Number II in Java: Fill Matching Ends
Generate upside-down-symmetric numbers by filling two ends together, handling leading zero and odd centers, with code and a visual dry run.
Read article →The Knight’s Tour in Java: Choose a Move, Explore, Undo
Find a complete knight tour with legal L moves, visited-state backtracking, success-preserving returns, a board example and tested Java.
Read article →Strobogrammatic Number III in Java: Count Numbers Between String Bounds
Count upside-down-symmetric numbers in an inclusive string range with paired-digit recursion, safe comparisons, commented Java and a dry run.
Read article →M-Coloring in Java: Can Every Neighbor Have a Different Color?
Solve graph coloring with tentative assignments, neighbor checks and backtracking; understand why a triangle needs three colors.
Read article →N-Queens in Java: Place One Queen per Row, Then Undo
Generate all nonattacking queen boards with row-by-row backtracking, explain diagonal keys and undo, and trace the two solutions for n=4.
Read article →Palindrome Partitioning in Java: Choose a Valid Prefix, Partition the Rest
Enumerate palindrome partitions by choosing valid prefixes, copying completed paths and undoing; understand substring costs and minimum-cut differences.
Read article →Rat in a Maze in Java: Explore Every Path Without Reusing Cells
Enumerate sorted maze paths with DFS, path-local visited cells and careful undo; handle blocked endpoints and preserve the input grid.
Read article →Sudoku Solver in Java: Try a Digit, Recurse, Restore on Failure
Solve Sudoku in place with first-empty-cell backtracking, explain row/column/box checks, and distinguish a safe trial from a complete solution.
Read article →Count Subsequences with Sum K in Java: Choices, Returns, and DP
Understand take-or-skip recursion, non-empty index choices, returned counts, and positive-target dynamic programming with commented Java and a real call tree.
Read article →Word Search in Java: Match Letters Along One Nonrepeating Path
Find a word through adjacent grid cells using path-local visited marks, short-circuit recursion and restoration, without reusing a cell.
Read article →Does a Subsequence with Sum K Exist? Java Recursion and DP
Learn why existence uses short-circuit returns, how take and skip reduce the remaining target, and how bounded subset-sum DP avoids repeated work.
Read article →Confusing Number II in Java: Build Valid Digits, Count Changed Rotations
Understand confusing numbers with digit rotation, valid-digit DFS, a complete recursion tree, commented Java, dry runs and justified complexity.
Read article →Generate Binary Strings Without Consecutive Ones in Java
Build only valid binary strings, understand every choose-and-undo step, and connect the recursion tree to Fibonacci counts and lexicographic order.
Read article →Robot Room Cleaner in Java: Explore Blindly, Return Safely
Derive blindfolded DFS using relative coordinates, keep the robot's direction synchronized, and follow physical backtracking through commented Java and a static dry run.
Read article →Palindrome Permutation II in Java: Build Half, Then Mirror
Understand odd frequencies, duplicate-free half permutations, shared state restoration, and a step-through recursion tree with fully commented Java.
Read article →Letter Combinations of a Phone Number in Java: One Digit, One Choice
Learn phone-keypad backtracking from first principles, with examples, commented Java, a numbered image dry run, state restoration and output-sensitive complexity.
Read article →Stepping Numbers in Java: Grow a Digit Tree Instead of Scanning a Range
Generate sorted stepping numbers with digit-based DFS, boundary checks, safe arithmetic, an actual recursion tree, and beginner-friendly Java explanations.
Read article →Combination Sum III in Java: Exactly k Distinct Digits
Understand exactly-k digit combinations with a subset baseline, take/skip recursion, safe sum bounds, commented Java and a complete illustrated dry run.
Read article →Expression Add Operators in Java: Backtrack Without Losing Precedence
Build every matching arithmetic expression with operand boundaries, signed last-term tracking, leading-zero guards, commented Java and an illustrated dry run.
Read article →Permutations III in Java: Alternate Odd and Even with Backtracking
Learn parity-constrained permutations with simple reasoning, commented Java, a recursion tree and dry runs showing choices, returns and undo.
Read article →PLANNED PRACTICE
What comes after the published lessons.
- Combination sumPlanned, not yet published
- PermutationsPlanned, not yet published
