Pattern this teaches:Backtracking with Constraints
Palindrome Partitioning
A medium Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 2
- Core for
- 0 roles
The problem
Cut a string into pieces so that every piece is a palindrome, meaning it reads the same in both directions. Return every possible way of doing the cuts.
Example 1
- Input
- s = "aab"
- Output
- [["a","a","b"], ["aa","b"]]
- Why
- Both ["a","a","b"] and ["aa","b"] are valid partitions where every substring is a palindrome.
Example 2
- Input
- s = "a"
- Output
- [["a"]]
- Why
- A single character is itself a palindrome, so the only partition is [["a"]].
Example 3
- Input
- s = "aba"
- Output
- [["a","b","a"], ["aba"]]
- Why
- Both ["a","b","a"] and ["aba"] are valid palindrome partitions.
Constraints
- 1 <= s.length <= 16
- S contains only lowercase English letters
How to think about it
Updated 2026-09-29A partition is a choice of cut positions along the string. If the prefix ending at a proposed cut is not a palindrome, cutting there is dead on arrival: prune immediately. Because sub-palindrome checks over identical intervals repeat across different cut sequences, caching palindrome intervals turns the validity check into an O(1) lookup.
Approaches, worst first
Backtracking with two-pointer check
time O(n * 2^n) · space O(n)
At start index i, try every end index j from i to n - 1. Run a two-pointer palindrome check on s[i..j]. If true, append substring to path, recurse on j + 1, and pop. Performs O(n) palindrome checks at every state.
Dynamic programming precomputationWrite this one
time O(n * 2^n) · space O(n^2)
Precompute a 2D boolean table isPal[i][j] in O(n^2) where isPal[i][j] is true if s[i] == s[j] and (j - i <= 2 or isPal[i + 1][j - 1]). Then backtrack with O(1) transition decisions, saving redundant character comparisons.
Where people lose marks · 3
- Off-by-one errors with substring slicing. In languages where slice(start, end) excludes end, passing j instead of j + 1 drops the last character of the candidate palindrome.
- DP table initialization order: computing isPal[i][j] top-down before isPal[i + 1][j - 1] is filled reads uninitialized false values.
- Pushing the working array into results by reference rather than creating a copy.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .