Palindrome Partitioning Using Backtracking in DSA C++

Mental Model

We try to split a string into parts where each part reads the same forwards and backwards. We explore all ways to do this by trying every possible cut and going back if it doesn't work.

Analogy: Imagine cutting a ribbon into pieces where each piece is a perfect mirror image of itself. You try one cut, check if the piece is a palindrome, then try the next cut. If a cut doesn't lead to a full solution, you undo it and try another.

s = "a b a b c"
Indices: 0 1 2 3 4
Partitions: [a] [b] [a] [b] [c]
Each [] is a palindrome piece
Backtracking tries cuts at each index to find all palindrome groups

Dry Run Walkthrough

Input: string: "aab"

Goal: Find all ways to split "aab" into palindrome parts

Step 1: Check substring from index 0 to 0: "a" is palindrome, add to current partition

["a"]

Why: Start with first character as a palindrome piece

Step 2: Recurse from index 1, check substring 1 to 1: "a" is palindrome, add to partition

["a", "a"]

Why: Next character alone is palindrome, continue building partition

Step 3: Recurse from index 2, check substring 2 to 2: "b" is palindrome, add to partition

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

Why: Last character alone is palindrome, partition complete

Step 4: Backtrack to index 1, try substring 1 to 2: "ab" is not palindrome, discard

["a"]

Why: Try longer substring but it is not palindrome, so backtrack

Step 5: Backtrack to index 0, try substring 0 to 1: "aa" is palindrome, add to partition

["aa"]

Why: Try bigger palindrome piece from start

Step 6: Recurse from index 2, check substring 2 to 2: "b" is palindrome, add to partition

["aa", "b"]

Why: Add last character as palindrome piece, partition complete

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool isPalindrome(const string &s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) return false; // mismatch means not palindrome
            start++;
            end--;
        }
        return true; // all matched means palindrome
    }

    void backtrack(const string &s, int start, vector<string> &current, vector<vector<string>> &result) {
        if (start == s.size()) {
            result.push_back(current); // reached end, save current partition
            return;
        }
        for (int end = start; end < s.size(); end++) {
            if (isPalindrome(s, start, end)) { // check palindrome substring
                current.push_back(s.substr(start, end - start + 1)); // choose this piece
                backtrack(s, end + 1, current, result); // explore further
                current.pop_back(); // undo choice to try next
            }
        }
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> current;
        backtrack(s, 0, current, result);
        return result;
    }
};

int main() {
    Solution sol;
    string input = "aab";
    vector<vector<string>> partitions = sol.partition(input);
    for (auto &partition : partitions) {
        for (auto &part : partition) {
            cout << part << " ";
        }
        cout << "\n";
    }
    return 0;
}

if (s[start] != s[end]) return false; // mismatch means not palindrome

Check characters from both ends to confirm palindrome

if (start == s.size()) { result.push_back(current); return; }

If reached end of string, save current partition as valid

if (isPalindrome(s, start, end)) { current.push_back(s.substr(start, end - start + 1)); backtrack(s, end + 1, current, result); current.pop_back(); }

Try every substring from start; if palindrome, choose it and recurse; then undo choice

Output

a a b 

aa b 

Complexity Analysis

Time: O(N * 2^N) because each character can be cut or not, and palindrome checks take O(N) each

Space: O(N) for recursion stack and current partition storage

vs Alternative: Naive approach tries all partitions without palindrome pruning, which is slower; backtracking prunes invalid paths early

Edge Cases

Empty string

Returns a list containing one empty partition

DSA C++

if (start == s.size()) { result.push_back(current); return; }

String with all identical characters, e.g. "aaa"

Finds all partitions with palindrome pieces like ["a", "a", "a"], ["aa", "a"], ["aaa"]

DSA C++

if (isPalindrome(s, start, end)) { ... }

String with no palindrome longer than 1, e.g. "abc"

Partitions only single characters as palindromes

DSA C++

if (isPalindrome(s, start, end)) { ... }

When to Use This Pattern

When asked to find all ways to split a string into palindrome parts, use backtracking to explore all partitions and prune non-palindromes early.

Common Mistakes

Mistake: Not checking palindrome before recursing, leading to invalid partitions
Fix: Add palindrome check before choosing substring to recurse

Mistake: Not undoing the choice (pop_back) after recursion, causing incorrect partitions
Fix: Always remove last chosen substring after recursive call to backtrack properly

Summary

Splits a string into all possible palindrome partitions using backtracking.

Use when you need to find all palindrome groupings of a string.

Try every cut, check palindrome, recurse, and undo to explore all valid partitions.

Practice

1. What is the main goal of palindrome partitioning using backtracking on a string s?

easy

A. To split s into substrings where each substring is a palindrome

B. To find the longest palindrome substring in s

C. To count the total number of palindromes in s

D. To reverse the string s using recursion

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing the string into parts where each part reads the same forwards and backwards.

2. Step 2: Role of backtracking

   Backtracking tries all possible partitions and keeps only those where every substring is a palindrome.

3. Final Answer:

   To split s into substrings where each substring is a palindrome -> Option A

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Remember: partition means split into palindrome parts [OK]

Common Mistakes:

• Confusing palindrome partitioning with finding longest palindrome
• Thinking it counts palindromes instead of partitioning
• Assuming it reverses the string

2. Which of the following is the correct base case check in a backtracking function for palindrome partitioning of string s starting at index start?

easy

A. if (start == s.length()) add current partition to result;

B. if (start > s.length()) return false;

C. if (start == s.length()) return true;

D. if (start < 0) return false;

Solution

1. Step 1: Understand base case in backtracking

   The base case occurs when the start index reaches the end of the string, meaning a full partition is formed.

2. Step 2: What to do at base case

   At this point, the current partition is a valid palindrome partition and should be added to the result list.

3. Final Answer:

   if (start == s.length()) add current partition to result; -> Option A

4. Quick Check:

   Base case adds partition when start reaches string end [OK]

Hint: Base case: start at string end means add partition [OK]

Common Mistakes:

• Returning true/false instead of adding partition
• Checking start > length instead of == length
• Using invalid index checks like start < 0

3. What is the output of the following C++ code snippet for palindrome partitioning?

void backtrack(string s, int start, vector<string>& path, vector& res) {
    if (start == s.size()) {
        res.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        string sub = s.substr(start, end - start + 1);
        string rev = sub;
        reverse(rev.begin(), rev.end());
        if (sub == rev) {
            path.push_back(sub);
            backtrack(s, end + 1, path, res);
            path.pop_back();
        }
    }
}

int main() {
    string s = "aab";
    vector res;
    vector<string> path;
    backtrack(s, 0, path, res);
    for (auto &v : res) {
        for (auto &str : v) cout << str << " ";
        cout << endl;
    }
    return 0;
}

medium

A. a a b \naab \naa b

B. a a b \naab

C. a a b \naa b

D. a a b

Solution

1. Step 1: Trace palindrome partitions of "aab"

   Possible palindrome partitions are ["a", "a", "b"] and ["aa", "b"].

2. Step 2: Check output format

   The code prints each partition on a new line with substrings separated by spaces, so output lines are "a a b" and "aa b".

3. Final Answer:

   a a b \naa b -> Option C

4. Quick Check:

   Partitions = ["a","a","b"], ["aa","b"] [OK]

Hint: List all palindrome splits, print each partition line [OK]

Common Mistakes:

• Missing the "aa" substring partition
• Printing partitions in wrong order
• Confusing substring boundaries

4. Identify the bug in this backtracking code snippet for palindrome partitioning:

void backtrack(string s, int start, vector<string>& path, vector& res) {
    if (start == s.size()) {
        res.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        string sub = s.substr(start, end - start + 1);
        if (isPalindrome(sub)) {
            path.push_back(sub);
            backtrack(s, end, path, res);  // Bug here
            path.pop_back();
        }
    }
}

medium

A. The substring extraction is incorrect

B. The recursive call should use end + 1 instead of end

C. The base case condition is wrong

D. The palindrome check function is missing

Solution

1. Step 1: Analyze recursive call index

   The recursive call uses end as the next start index, but it should move past the current substring.

2. Step 2: Correct index to avoid infinite loop

   Using end + 1 ensures the next substring starts after the current one, preventing repeated processing.

3. Final Answer:

   The recursive call should use end + 1 instead of end -> Option B

4. Quick Check:

   Next start index = end + 1 to avoid overlap [OK]

Hint: Next start index must skip current substring end [OK]

Common Mistakes:

• Using end instead of end + 1 causes infinite recursion
• Ignoring base case correctness
• Assuming substring extraction is wrong

5. Given the string s = "racecarannakayak", how many palindrome partitions can be formed using backtracking? (Assume all partitions are valid palindrome splits.)

hard

A. 5

B. 12

C. 10

D. 8

Solution

1. Step 1: Identify palindromic substrings in s

   Substrings like "racecar", "anna", "kayak" are palindromes. Smaller palindromes like "a", "c", "r" also exist.

2. Step 2: Count partitions using backtracking

   Backtracking explores all splits where each substring is palindrome. For this string, there are 8 valid partitions combining these palindromes.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   Backtracking counts 8 palindrome partitions for given string [OK]

Hint: Count all palindrome splits including big and small palindromes [OK]

Common Mistakes:

• Counting only large palindromes
• Missing smaller palindrome partitions
• Assuming fewer partitions than actual