Palindrome Partitioning Using Backtracking in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Partitioning for "aab"

What is the output of the following C++ code that finds all palindrome partitions of the string "aab" using backtracking?

DSA C++

void backtrack(string s, int start, vector<string>& current, vector<vector<string>>& result) {
    if (start == s.size()) {
        result.push_back(current);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        bool palindrome = true;
        for (int i = start, j = end; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                palindrome = false;
                break;
            }
        }
        if (palindrome) {
            current.push_back(s.substr(start, end - start + 1));
            backtrack(s, end + 1, current, result);
            current.pop_back();
        }
    }
}

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

int main() {
    string s = "aab";
    vector<vector<string>> res = partition(s);
    for (auto &v : res) {
        for (auto &str : v) {
            cout << str << " ";
        }
        cout << "\n";
    }
    return 0;
}

A [["a", "ab"]]

B [["aab"]]

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

D [["aa", "b"], ["a", "a", "b"], ["a", "ab"]]

💡 Hint

Check all substrings that are palindromes and explore partitions recursively.

The code finds all palindrome partitions of "aab". The palindromes are "a", "a", "b" and "aa", "b". So the output lists these partitions.

🧠 Conceptual

intermediate

Number of Palindrome Partitions for "racecar"

How many palindrome partitions does the string "racecar" have when using backtracking to find all partitions?

A 6

B 12

C 10

D 4

💡 Hint

Consider all palindromic substrings and how they combine.

The string "racecar" has 4 palindrome partitions including single letters and longer palindromes like "racecar" itself.

🔧 Debug

advanced

Identify the Error in Palindrome Partitioning Code

What error will the following code produce when trying to find palindrome partitions of "abc"? void backtrack(string s, int start, vector& current, vector>& result) { if (start > s.size()) { result.push_back(current); return; } for (int end = start; end < s.size(); ++end) { bool palindrome = true; for (int i = start, j = end; i < j; ++i, --j) { if (s[i] != s[j]) { palindrome = false; break; } } if (palindrome) { current.push_back(s.substr(start, end - start + 1)); backtrack(s, end + 1, current, result); current.pop_back(); } } }

A No partitions added due to incorrect base case

B No error, works correctly

C Out of range error accessing string

D Compilation error due to missing return type

💡 Hint

Check the base case condition carefully.

The base case uses 'start > s.size()', but it should be 'start == s.size()' to stop recursion properly. Otherwise, no partitions are added because the base case never triggers.

🚀 Application

advanced

Find the Palindrome Partitioning of "noon"

Which of the following lists contains all palindrome partitions of the string "noon"?

A [["n", "o", "on"], ["no", "on"]]

B [["n", "o", "o", "n"], ["n", "oo", "n"], ["noon"]]

C [["noon"]]

D [["n", "oo", "n"], ["n", "o", "o", "n"]]

💡 Hint

Check all substrings that are palindromes: single letters, "oo", and "noon".

The palindromic partitions are single letters, the middle "oo", and the whole string "noon".

❓ Predict Output

expert

Output of Palindrome Partitioning for "abba"

What is the output of the following C++ code that finds all palindrome partitions of the string "abba" using backtracking? #include #include #include using namespace std; bool isPalindrome(const string& s, int start, int end) { while (start < end) { if (s[start++] != s[end--]) return false; } return true; } void backtrack(const string& s, int start, vector& current, vector>& result) { if (start == s.size()) { result.push_back(current); return; } for (int end = start; end < s.size(); ++end) { if (isPalindrome(s, start, end)) { current.push_back(s.substr(start, end - start + 1)); backtrack(s, end + 1, current, result); current.pop_back(); } } } int main() { string s = "abba"; vector> result; vector current; backtrack(s, 0, current, result); for (auto& partition : result) { for (auto& str : partition) { cout << str << " "; } cout << "\n"; } return 0; }

A [["a", "b", "b", "a"], ["a", "bb", "a"], ["abba"]]

B [["a", "b", "b", "a"], ["ab", "ba"]]

C [["abba"]]

D [["a", "bb", "a"]]

💡 Hint

Check all palindromic substrings including single letters, "bb", and the whole string.

The palindrome partitions of "abba" are the single letters, the middle "bb", and the entire string "abba".

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