题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

代码

 1 class Solution {
 2 public:
 3     vector<vector<string>>res;
 4     vector<string>path;
 5     bool check(string s,int start,int end){
 6         for(int i = start,j = end;i <= j;i++,j--){
 7             if(s[i] != s[j]) return false;
 8         }
 9         return true;
10     }
11     void backtracking(string s,int startIndex){
12         if(startIndex >= s.size()){
13             res.push_back(path);
14             return;
15         }
16         for(int i = startIndex;i < s.size();i++){
17             if(check(s,startIndex,i)){
18                 path.push_back(s.substr(startIndex,i-startIndex+1));
19             }else{
20                 continue;
21             }
22             backtracking(s,i+1);
23             path.pop_back();
24         }
25 
26     }
27     vector<vector<string>> partition(string s) {
28         backtracking(s,0);
29         return res;
30     }
31 };

切割过的地方不能重复切割，所以需要startIndex。

分割问题，也可看成回溯