1
class Solution {
2
 public:
3
  bool check(string k) {
4
    string l = k;
5
    reverse(l.begin(), l.end());
6
    if (k == l) return true;
7
    return false;
8
  }
9
  void solve(string &s, vector<vector<string>> &ans, vector<string> temp, int pos) {
10
    if (pos >= s.size()) {
11
      ans.push_back(temp);
12
      return;
13
    }
14
    string m;
15
    for (int i = pos; i < s.size(); i++) {
16
      m += s[i];
17
      if (check(m)) {
18
        temp.push_back(m);
19
        solve(s, ans, temp, i + 1);
20
        temp.pop_back();
21
      }
22
    }
23
  }
24
  vector<vector<string>> partition(string s) {
25
    vector<vector<string>> ans;
26
    vector<string> temp;
27
    solve(s, ans, temp, 0);
28
    return ans;
29
  }
30
};