Palindrome Partitioning

MediumBacktracking · DP🧩 Backtracking LeetCode #131 ↗Updated Oct 30, 2026

Problem

Cut a string s into consecutive pieces so that every piece is a palindrome. Return all such partitions (any order).

Input"aab"Output[[a,a,b],[aa,b]]

1 ≤ s.length ≤ 16 · lowercase English letters only

Try it yourself

Java

class Solution {
    public List<List<String>> partition(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Decide the first piece s[start..end]; if it is a palindrome, the rest is the same problem on s[end+1..]. A precomputed palindrome table makes each check O(1).

PatternBacktracking

Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.

Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.

Open the Backtracking guide →

Approaches

Brute ForceAll 2^n-1 Cut Patterns, Then Filter

Time O(n · 2ⁿ)Space O(n) extra

Between each adjacent pair of characters there is a cut or not, so a bitmask of n-1 bits describes every partition. Split by each mask and keep it only if all pieces are palindromes.

Java

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    int n = s.length();
    for (int mask = 0; mask < (1 << (n - 1)); mask++) {
        List<String> parts = new ArrayList<>();
        int start = 0;
        boolean ok = true;
        for (int i = 0; i < n && ok; i++) {
            if (i == n - 1 || (mask & (1 << i)) != 0) {
                ok = isPal(s, start, i);
                parts.add(s.substring(start, i + 1));
                start = i + 1;
            }
        }
        if (ok) res.add(parts);
    }
    return res;
}
private boolean isPal(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

Always pays for all 2^n-1 partitions, valid or not.

BetterBacktracking with On-the-Fly Check

Time O(n · 2ⁿ)Space O(n) extra

From start, try every end; recurse only if s[start..end] is a palindrome, then undo. Dead prefixes are pruned, but the same substring may be re-checked in many branches.

Java

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), res);
    return res;
}
private void backtrack(String s, int start, List<String> cur, List<List<String>> res) {
    if (start == s.length()) { res.add(new ArrayList<>(cur)); return; }
    for (int end = start; end < s.length(); end++) {
        if (isPal(s, start, end)) {
            cur.add(s.substring(start, end + 1));
            backtrack(s, end + 1, cur, res);
            cur.remove(cur.size() - 1); // undo
        }
    }
}
private boolean isPal(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

Prunes dead branches; worst case (e.g. "aaaa") is still exponential.

OptimalDP Palindrome Table + Backtracking

Time O(n · 2ⁿ)Space O(n²)

Precompute dp[i][j] in O(n²): s[i..j] is a palindrome iff its ends match and dp[i+1][j-1] holds (so fill i right to left). Backtracking then checks any piece in O(1).

Java

public List<List<String>> partition(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1]);
    List<List<String>> res = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), res, dp);
    return res;
}
private void backtrack(String s, int start, List<String> cur,
                       List<List<String>> res, boolean[][] dp) {
    if (start == s.length()) { res.add(new ArrayList<>(cur)); return; }
    for (int end = start; end < s.length(); end++) {
        if (!dp[start][end]) continue; // O(1) check
        cur.add(s.substring(start, end + 1));
        backtrack(s, end + 1, cur, res, dp);
        cur.remove(cur.size() - 1);
    }
}

Same worst case (the output itself is exponential) but no repeated checks.

At a glance

Level	Approach	Time	Space
Brute Force	All 2^n-1 Cut Patterns, Then Filter	`O(n · 2ⁿ)`	`O(n) extra`
Better	Backtracking with On-the-Fly Check	`O(n · 2ⁿ)`	`O(n) extra`
Optimal	DP Palindrome Table + Backtracking	`O(n · 2ⁿ)`	`O(n²)`

Common pitfalls

Filling the DP table top-down by i — reads dp[i+1] before it exists.
Base case off by one: lengths 1–3 need only s[i]==s[j].
Adding cur itself instead of new ArrayList<>(cur).

Interview tips

Worst case is all-equal letters: 2^n-1 partitions, so exponential is unavoidable.
Present plain backtracking first, then add the DP table as an optimisation.
Link it to Palindrome Partitioning II, where the same table drives a min-cut DP.

Pattern

Backtracking over cut positions → enumerate ways to split a string/array into valid pieces.

My notes saved in this browser