Palindrome Partitioning

1. Problem Statement and Objective

The objective of the Palindrome Partitioning problem is to take a given input string $s$ and partition it in all possible ways such that every individual substring in a given partition is a palindrome.

A palindrome string is defined as a string that reads the same forwards and backwards (e.g., "a", "aa", "aba"). The final output must be a collection (a list of lists) containing all valid partition combinations.

Real-Life Analogy: Cutting a Ribbon into Palindromic Segments

Imagine you have a colorful strip of fabric or ribbon with letters printed on it. Your goal is to use scissors to make cuts across the strip so that every single piece you cut off reads the exact same forwards and backwards. You are asked to find every possible combination of cuts that achieves this valid condition, and then display all the resulting sets of pieces.

2. Input Constraints and Brute-Force Intuition

• String Length Constraint: The maximum length of string $s$ is typically up to $16$ in standard competitive programming variations.
• Why Recursion?: Because we need to explore all possible positions to make cuts, and each valid cut leaves us with a smaller remaining substring that requires the exact same partitioning logic, this naturally lends itself to a recursive exploration tree with backtracking.

3. Core Mental Model: Step-by-Step Partitioning Decisions

When given a string like s = "aab", we evaluate potential cut locations from left to right:

1. First Cut Option: We check if the prefix from the current index to index $i$ is a palindrome.
   • If substring s[index...i] is a palindrome, we make a cut, store that substring into our current path list, and recursively solve for the remaining substring starting at i + 1.
   • If s[index...i] is NOT a palindrome, we cannot make a cut here, so we skip it and expand our prefix boundary (i).

Example Trace for s = "aab"

• Try cutting at index $0$ ("a" is a palindrome) -> Recurse on remaining "abb".
• Try cutting at index $1$ ("aa" is a palindrome) -> Recurse on remaining "b".
• Try cutting at index $2$ ("aab" is NOT a palindrome) -> Skip.

4. Visualizing the Recursive Backtracking Tree

5. The Pseudo-Code Framework

The algorithm relies on a helper function that loops through possible end indices starting from our current pointer, validates palindromes, recurses, and backtracks.

def partition(s):
    res = []
    
    def backtrack(index, path):
        # Base Case: If index reaches the end of the string
        if index == len(s):
            res.append(list(path))
            return
            
        # Try every possible partition point 'i' from index to end of string
        for i in range(index, len(s)):
            if isPalindrome(s, index, i):
                # 1. Action: Choose the valid palindromic substring
                path.append(s[index: i + 1])
                
                # 2. Recurse: Move to the next index
                backtrack(i + 1, path)
                
                # 3. Backtrack: Undo the choice to explore other partitions
                path.pop()

    backtrack(0, [])
    return res

6. Java Implementation

Below is the complete, production-ready Java solution demonstrating the recursive partitioning and backtracking mechanism with reference state modification (path.remove(...)).

import java.util.ArrayList;
import java.util.List;

public class PalindromePartitioning {
    
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        backtrack(0, s, path, res);
        return res;
    }
    
    private void backtrack(int index, String s, List<String> path, List<List<String>> res) {
        // Base Case: Reached the end of the string
        if (index == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        
        // Try partitioning from index to the end of the string
        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                // Choose: Add substring to current path
                path.add(s.substring(index, i + 1));
                
                // Explore: Recurse for the remaining substring starting at i + 1
                backtrack(i + 1, s, path, res);
                
                // Un-choose (Backtrack): Remove last element to explore other partitions
                path.remove(path.size() - 1);
            }
        }
    }
    
    private boolean isPalindrome(String s, int start, int end) {
        while (start <= end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}

7. C++ Implementation

Below is the complete, high-performance C++ solution utilizing standard vectors and reference passing for backtracking.

#include <vector>
#include <string>

using namespace std;

class PalindromePartitioning {
private:
    bool isPalindrome(string& s, int start, int end) {
        while (start <= end) {
            if (s[start++] != s[end--]) {
                return false;
            }
        }
        return true;
    }

    void backtrack(int index, string& s, vector<string>& path, vector<vector<string>>& res) {
        // Base Case: Reached the end of the string
        if (index == s.size()) {
            res.push_back(path);
            return;
        }

        // Try partitioning from index to the end of the string
        for (int i = index; i < s.size(); ++i) {
            if (isPalindrome(s, index, i)) {
                // Choose: Push substring into path
                path.push_back(s.substr(index, i - index + 1));

                // Explore: Recurse for the remaining substring
                backtrack(i + 1, s, path, res);

                // Un-choose (Backtrack): Pop back to restore state
                path.pop_back();
            }
        }
    }

public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> path;
        backtrack(0, s, path, res);
        return res;
    }
};

8. Summary Comparison of Implementation Details

9. Summary and Key Takeaways

• Problem Nature: Palindrome Partitioning is a classic combinatorial search problem solved effectively using Recursion and Backtracking.
• State Exploration: At every recursive step, we iterate through all possible cut endpoints (i from index to s.length() - 1).
• Palindrome Validation: We only proceed down a recursive branch if the prefix substring s[index...i] is confirmed to be a palindrome.
• Base Condition: When our pointer (index) reaches the end of string s, we have successfully formed a valid partition set, which we deep-copy and add to our final results list.
• The Importance of Backtracking: Because data structures (path) are passed by reference across recursive stack frames, cleaning up state (via .pop() or .remove()) after recursion returns is mandatory to prevent cross-contamination between different partition branches.