
## 题目地址

https://leetcode.com/problems/palindrome-partitioning/description/

## 题目描述

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

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

```

## 思路

这是一道求解所有可能性的题目， 这时候可以考虑使用回溯法。 回溯法解题的模板我们已经在很多题目中用过了，
这里就不多说了。大家可以结合其他几道题目加深一下理解。


## 关键点解析

- 回溯法

## 代码

* 语言支持：JS，Python3

```js


/*
 * @lc app=leetcode id=131 lang=javascript
 *
 * [131] Palindrome Partitioning
 */

function isPalindrom(s) {
    let left = 0;
    let right = s.length - 1;

    while(left < right && s[left] === s[right]) {
        left++;
        right--;
    }

    return left >= right;
}
 function backtrack(s, list, tempList, start) {
    const sliced = s.slice(start);

    if (isPalindrom(sliced) && (tempList.join("").length === s.length)) list.push([...tempList]);

    for(let i = 0; i < sliced.length; i++) {
        const sub = sliced.slice(0, i + 1);
        if (isPalindrom(sub)) {
            tempList.push(sub);
        } else {
            continue;
        }
        backtrack(s, list, tempList, start + i + 1);
        tempList.pop();
    }
 }
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    // "aab"
    // ["aa", "b"]
    // ["a", "a", "b"]
    const list = [];
    backtrack(s, list, [], 0);
    return list;
};


```
```python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        """回溯法"""
        
        res = []
        
        def helper(s, tmp):
            """
            如果是空字符串，说明已经处理完毕
            否则逐个字符往前测试，判断是否是回文
            如果是，则处理剩余字符串，并将已经得到的列表作为参数
            """
            if not s:
                res.append(tmp)
            for i in range(1, len(s) + 1):
                if s[:i] == s[:i][::-1]:
                    helper(s[i:], tmp + [s[:i]])
        
        helper(s, [])
        return res
```

## 相关题目
- [39.combination-sum](./39.combination-sum.md)
- [40.combination-sum-ii](./40.combination-sum-ii.md)
- [46.permutations](./46.permutations.md)
- [47.permutations-ii](./47.permutations-ii.md)
- [78.subsets](./78.subsets.md)
- [90.subsets-ii](./90.subsets-ii.md)
- [113.path-sum-ii](./113.path-sum-ii.md)

