# 1. Introduction

This blog post explores a fascinating string processing problem in C++ known as Palindrome Partitioning. The challenge is to partition a given string such that every substring of the partition is a palindrome. This problem is a great example of the use of backtracking and recursion in algorithm design.

## Problem

Given a string s, the task is to partition s in such a way that every substring of the partition is a palindrome. We need to return all possible palindrome partitioning of s.

Example 1:

- Input: s = "aab"

- Output: [["a","a","b"],["aa","b"]]

Example 2:

- Input: s = "a"

- Output: [["a"]]

# 2. Solution Steps

1. Use backtracking to explore all possible partitions of the string.

2. Check if the current substring is a palindrome.

3. If it is, add it to the current partition and recurse for the remaining string.

4. Backtrack and try different partitions.

5. Store each valid partitioning that consists only of palindromes.

# 3. Code Program

``````#include <iostream>
#include <vector>
using namespace std;

// Function to check if a substring is a palindrome
bool isPalindrome(const string &s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) return false;
}
return true;
}

// Helper function for backtracking
void backtrack(vector<vector<string>> &result, vector<string> &current, string &s, int start) {
if (start >= s.length()) {
result.push_back(current);
return;
}

for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
current.push_back(s.substr(start, end - start + 1));
backtrack(result, current, s, end + 1);
current.pop_back(); // Backtrack
}
}
}

// Function to partition string into all possible palindrome partitioning
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> current;
backtrack(result, current, s, 0);
return result;
}

int main() {
string s = "aab";
vector<vector<string>> partitions = partition(s);
cout << "Palindrome partitions:" << endl;
for (const auto &part : partitions) {
for (const string &str : part) {
cout << str << " ";
}
cout << endl;
}
return 0;
}
``````

### Output:

```Palindrome partitions:
a a b
aa b
```

### Explanation:

1. The input string "aab" is used for generating palindrome partitions.

2. The function explores all substrings, checking for palindromes and partitioning accordingly.

3. For "aab", it finds two valid partitions: ["a", "a", "b"] and ["aa", "b"].

4. Each partition is a combination where every substring is a palindrome.

5. The use of backtracking allows the function to explore all possible partitions and collect those that satisfy the palindrome condition.