Palindrome Partitioning | Backtracking

Problem Statement

Given a string s, partition it such that every substring of the partition is a palindrome.

Return all possible palindrome partitionings.

---

Brute Force Intuition

We can generate every possible partition of the string and then check whether every substring in that partition is a palindrome.

For a string of length N, the number of possible partitions grows exponentially, making brute force expensive.

Complexity

• Time Complexity: O(2ᴺ × N)
• Space Complexity: O(N)

---

Moving Towards the Optimal Approach

Instead of generating all partitions first and validating later, we can validate while building the partition.

At every index:

Try all possible substrings

If a substring is a palindrome:

Choose it
Recurse on remaining string
Backtrack

This avoids exploring many invalid paths.

---

Pattern Recognition

Whenever you see:

• Generate all valid partitions
• String partitioning
• Constraints on each partition

Think:

Backtracking + Validation

---

Key Observation

For:

s = "aab"

At index 0, possible cuts are:

"a"   ✅
"aa"  ✅
"aab" ❌

Only palindrome substrings should be considered.

---

Recursive Decision Tree

"aab"

                []
              /    \
            "a"    "aa"
             |       |
           ["a"]  ["aa"]
             |       |
            "a"      "b"
             |       |
        ["a","a"] ["aa","b"]
             |
            "b"
             |
      ["a","a","b"]

Valid answers:

["a","a","b"]
["aa","b"]

---

Optimal Java Solution

import java.util.*;

class Solution {

    public List<List<String>> partition(String s) {

        List<List<String>> ans = new ArrayList<>();

        helper(0, s, new ArrayList<>(), ans);

        return ans;
    }

    private void helper(int index,
                        String s,
                        List<String> temp,
                        List<List<String>> ans) {

        if (index == s.length()) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int end = index; end < s.length(); end++) {

            if (isPalindrome(index, end, s)) {

                temp.add(s.substring(index, end + 1));

                helper(end + 1, s, temp, ans);

                temp.remove(temp.size() - 1);
            }
        }
    }

    private boolean isPalindrome(int i, int j, String s) {

        while (i < j) {

            if (s.charAt(i) != s.charAt(j))
                return false;

            i++;
            j--;
        }

        return true;
    }
}

---

Dry Run

Input

s = "aab"

Step 1

Choose "a"

Current Partition:

["a"]

Remaining:

"ab"

---

Step 2

Choose "a"

Current Partition:

["a","a"]

Remaining:

"b"

---

Step 3

Choose "b"

Current Partition:

["a","a","b"]

Valid Answer

---

Another Path

Start with:

"aa"

Current Partition:

["aa"]

Then:

["aa","b"]

Valid Answer

---

Output

[
    ["a","a","b"],
    ["aa","b"]
]

---

Why Backtracking Works?

At every position we try every possible cut:

index → end

If the chosen substring is a palindrome:

Take it
Explore further
Undo choice

This guarantees all valid partitions are generated exactly once.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N × 2ᴺ)
Space Complexity	O(N)

The recursion generates exponentially many partitions in the worst case.

---

Interview One-Liner

At every index, try all possible substrings. If a substring is a palindrome, include it in the current partition and recursively solve for the remaining string.

---

Pattern Learned

Generate All Valid Partitions
+
Validate Each Choice
+
Backtrack

=> Backtracking

Similar Problems

• Palindrome Partitioning
• Restore IP Addresses
• Word Break II
• N Queens
• Combination Sum
• Subsets

---

Memory Trick

Palindrome Partitioning is not a Pick / Not Pick problem.

Think:

Start Index
    ↓
Try Every Possible Cut
    ↓
Palindrome?
    ↓
Yes → Take
No  → Skip

Mental Model

Subsets
→ Pick / Not Pick

Combination Sum
→ Pick / Not Pick

Palindrome Partitioning
→ Try Every Cut
→ Validate Cut
→ Recurse

Once you recognize "Generate all valid partitions", your brain should immediately think:

Backtracking + Try Every Cut + Palindrome Check