From
Leetcode
Status
AC
Date
Mar 13, 2024
Tags
分割
回溯
递归
动态规划
Difficulty
困难
题面
给你一个字符串
s，请你将 s 分割成一些子串，使每个子串都是回文串
。返回
所有可能的分割方案。
示例 1：
示例 2：
提示：
1 <= s.length <= 16
s仅由小写英文字母组成
思路
- 切割问题可以抽象为组合问题
- 如何模拟那些切割线
- 切割问题中递归如何终止
- 在递归循环中如何截取子串
- 如何判断回文
题解
- python版且使用all函数
- C++版动态规划判断回文数
- Python版动态规划优化回文判断
回溯简洁版
如果 path 的长度不固定，或者每次递归到 i，path【i】 不一定会被修改，就需要恢复现场。