问题：

给定一个字符串，进行切分，使得每个切片都是一个回文字符串。将所有切法返回。

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.

　　

解法：Backtracking（回溯算法）

对于本问题，两个变量：

• 路径：已经切好的前几位结果
• 选择列表：对每个位置上可选择切分or不切，若满足回文字符串，则进行下一个位置的递归判断

处理过程：

base：递归退出条件：选择到最后一位结束，这里为当前位置pos==给出的字符串长度。

• 将path加入res中，返回。

做选择：从当前位置pos开始，向后找字符串tmp=s[pos～i]，满足回文字符串的话，进行选择

• 路径.add(tmp)
• 选择列表：pos=pos+i

撤销选择：回退到选择tmp字符串之前的状况。

• 路径.delete(tmp)
• 选择列表：pos=pos-i

 

代码参考：

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