## Algorithm

Problem Name: 131. Palindrome Partitioning

Given a string `s`, partition `s` such that every substringof the partition is a palindrome 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"]]
```

Constraints:

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int start;
int len;
} buff_t;
typedef struct {
char ***p;
int *csz;
int psz;
int pn;
} res_t;
void add2res(res_t *res, const char *s, buff_t *buff, int d) {
int i;
char *str, **pp;
if (res->psz == res->pn) {
res->psz = (res->psz == 0) ? 10 : res->psz * 2;
res->p = realloc(res->p, res->psz * sizeof(char **));
res->csz = realloc(res->csz, res->psz * sizeof(int));
//assert(res->p && res->psz);
}
pp = malloc(d * sizeof(char *));
//assert(pp);
for (i = 0; i  <  d; i ++) {
str = strndup(&s[buff[i].start], buff[i].len);
pp[i] = str;
}
res->p[res->pn] = pp;
res->csz[res->pn ++] = d;
}
int is_palindrome(const char *s, int start, int end) {
while (start  <  end) {
if (s[start] != s[end]) return 0;
start ++;
end --;
}
return 1;
}
void bt(const char *s, int start, int sz, buff_t *buff, int d, res_t *res) {
int i;
if (start == sz) {
// done, save result
return;
}
for (i = start; i  <  sz; i ++) {
if (is_palindrome(s, start, i)) {
buff[d].start = start;
buff[d].len = i - start + 1;
bt(s, i + 1, sz, buff, d + 1, res);
}
}
}
char*** partition(char* s, int** columnSizes, int* returnSize) {
res_t res = { 0 };
buff_t *buff;
int sz;

sz = strlen(s);

buff = malloc(sz * sizeof(buff_t));
//assert(buff);

bt(s, 0, sz, buff, 0, &res);

//free(buff);

*columnSizes = res.csz;
*returnSize = res.pn;

return res.p;
}
``````
Copy The Code &

Input

cmd
s = "aab"

Output

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

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector < vector<string>>res;
vector < string>v;
dfs(s, 0, v, res);
return res;
}

void dfs(string s, int pos, vector < string>& v, vector<vector<string>>& res){
if(pos >= s.size()){
res.push_back(v);
return;
}

for(int i = pos; i < s.size(); i++){
int l = pos, r = i;
bool b = true;
while(l  <  r && b) if(s[l++] != s[r--]) b = false;
if(b){
v.push_back(s.substr(pos, i - pos + 1));
dfs(s, i + 1, v, res);
v.pop_back(>;
}
}
}
};

``````
Copy The Code &

Input

cmd
s = "aab"

Output

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

### #3 Code Example with Java Programming

```Code - Java Programming```

``````start coding...
class Solution {
public List();
helper(ans, new ArrayList(), a, 0);
return ans;
}

private void helper(List < List temp, String a, int idx) {
if (idx == a.length()) {
return;
}
for (int i=idx; i < a.length(); i++) {
String sb = a.substring(idx, i+1);

if (isPalindrome(sb)) {
helper(ans, temp, a, i+1);
temp.remove(temp.size()-1);
}
}
}

private boolean isPalindrome(String s) {
return new StringBuilder(s).reverse().toString().equals(s);
}
}
``````
Copy The Code &

Input

cmd
s = "a"

Output

cmd
[["a"]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const partition = function(s) {
let res = []
backtrack(res, [], 0, s)
return res
}

function backtrack(res, cur, start, s) {
if (start === s.length) res.push([...cur])
else {
for (let i = start; i  <  s.length; i++) {
if (isPalindrome(s, start, i)) {
cur.push(s.substring(start, i + 1))
backtrack(res, cur, i + 1, s)
cur.pop()
}
}
}
}

function isPalindrome(str, start, i) {
let l = start,
r = i
while (l < r) {
if (str[l] !== str[r]) return false
l++
r--
}
return true
}
``````
Copy The Code &

Input

cmd
s = "a"

Output

cmd
[["a"]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def partition(self, s):
q, n = [[s[0]]], len(s)
for i in range(1, n):
new = []
for arr in q:
cur = arr[-1] + s[i]
if i < n - 1 or cur == cur[::-1]:
new.append(arr[:-1] + [cur])
if arr[-1] == arr[-1][::-1]:
new.append(arr + [s[i]])
q = new
return q
``````
Copy The Code &

Input

cmd
s = "aab"

Output

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

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0131_PalindromePartitioning
{
public IList < IList(), results, dp, 0, s);
return results;
}

private void GenerateResult(List < string> current_result, List(current_result));
return;
}

for (int i = position; i  <  s.Length; i++)
{
if (dp[position, i])
{
current_result.Add(s.Substring(position, i - position + 1));
GenerateResult(current_result, results, dp, i + 1, s);
current_result.RemoveAt(current_result.Count - 1);
}
}
}
}
}
``````
Copy The Code &

Input

cmd
s = "aab"

Output

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