给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[ ["aa","b"], ["a","a","b"] ]
方法1：递归
class Solution:
def partition(self, s: str) -> List[List[str]]:
if not s:
return [[]]
if len(s) == 1:
return [[s]]
ret = []
for i in range(1, len(s)+1):
if s[:i][::-1] == s[:i]:
ret += [[s[:i]]+j for j in self.partition(s[i:])]
return ret
方法2：回溯
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
原文：https://www.cnblogs.com/USTC-ZCC/p/13171420.html