Palindrome Partitioning Using Backtracking in DSA C++ - Build from Scratch

Palindrome Partitioning Using Backtracking

📖 Scenario: Imagine you have a word, and you want to split it into parts where each part reads the same forwards and backwards. This is called palindrome partitioning. For example, the word "noon" can be split as "n" | "oo" | "n" or "noon" itself.

🎯 Goal: You will build a program that finds all possible ways to split a given word into palindrome parts using backtracking. This helps understand how to explore all options step-by-step and check conditions.

📋 What You'll Learn

Create a string variable with a specific word

Create a helper function to check if a substring is a palindrome

Use backtracking to find all palindrome partitions

Print all palindrome partitions found

💡 Why This Matters

🌍 Real World

Palindrome partitioning helps in text processing, DNA sequence analysis, and finding symmetrical patterns in data.

💼 Career

Understanding backtracking and palindrome checks is useful for software engineers working on algorithms, coding interviews, and problem-solving tasks.

1

Create the input string

Create a string variable called s and set it to the exact value "aab".

DSA C++

# Create the string variable s with value "aab"
# Your code here

Hint

Use std::string s = "aab"; to create the string.

2

Write a palindrome check function

Write a function called isPalindrome that takes two integers start and end and returns true if the substring of s from start to end is a palindrome, otherwise false. Use a while loop to compare characters.

DSA C++

std::string s = "aab";

// Write the isPalindrome function below
// Your code here

Hint

Compare characters from the start and end moving towards the center.

3

Implement backtracking to find palindrome partitions

Write a function called backtrack that takes an integer start and a vector of strings current. Use a for loop with variable end from start to s.size() - 1. Inside the loop, check if substring s[start..end] is palindrome using isPalindrome. If yes, add substring s.substr(start, end - start + 1) to current, call backtrack recursively with end + 1, then remove the last element from current to backtrack. When start == s.size(), add current to a global vector result.

DSA C++

std::string s = "aab";

bool isPalindrome(int start, int end) {
    while (start 
#include 

std::vector> result;

// Write the backtrack function below
// Your code here

Hint

Use recursion and backtracking to explore all palindrome partitions.

4

Print all palindrome partitions

Create a vector of strings called current. Call backtrack(0, current). Then use a for loop with variable partition to iterate over result. Inside, use another for loop with variable part to print each string in partition separated by spaces. Print a new line after each partition.

DSA C++

std::string s = "aab";

bool isPalindrome(int start, int end) {
    while (start 
#include 
#include 

std::vector> result;

void backtrack(int start, std::vector& current) {
    if (start == s.size()) {
        result.push_back(current);
        return;
    }
    for (int end = start; end < s.size(); end++) {
        if (isPalindrome(start, end)) {
            current.push_back(s.substr(start, end - start + 1));
            backtrack(end + 1, current);
            current.pop_back();
        }
    }
}

// Print all palindrome partitions below
// Your code here

Hint

Use nested loops to print each partition and its parts separated by spaces.

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