# 131. Palindrome Partitioning LeetCode | CodingKaro

## 131. Palindrome Partitioning

Given a string `s`, partition `s` such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of `s`.

palindrome string is a string that reads the same backward as forward.

Example 1:

```Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
```

Example 2:

```Input: s = "a"
Output: [["a"]]
```

Constraints:

• `1 <= s.length <= 16`
• `s` contains only lowercase English letters.

### The solution to the above problem is

class Solution {
public:
vector<vector<string>>ans;
bool checkPalindrome(string s,int start,int end){
while(start<=end){
if(s[start]!=s[end]){
return false;
}

start++;
end--;
}
return true;
}

void helper(string s,int t,vector<string>&temp){
if(t==s.size()){
ans.push_back(temp);
return;
}
for(int i=t; i<s.length(); i++){
if(checkPalindrome(s,t,i)){
temp.push_back(s.substr(t,i-t+1));
helper(s,i+1,temp);
temp.pop_back();
}
}

}

vector<vector<string>> partition(string s) {
vector<string>v;
helper(s,0,v);
return ans;
}
};