1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class Solution {
public:
    vector<vector<string>> ans;
    vector<vector<string>> partition(string s) {
        ans.clear();
        if(s.length() <= 0) return ans;
        bool *flag = new bool[s.length()+1];
        for(int i = 0; i <= s.length(); i++)
            flag[i] = false;
        flag[0] = true;
        PartitionStep(s, 1, flag);
        return ans;
    }
private:
    void PartitionStep(string s, int step, bool *flag) {
        if(step == s.length()) {
            int i;
            flag[step] = true;
            for(i = step-1; i >= 0; i--) {
                if(flag[i] == true) break;
            }
            if(IsPalindrome(s, i, step-1)) {
                GenAnsItem(s, flag);
            }
            flag[step] = false;
            return;
        }
        flag[step] = true;
        int i;
        for(i = step-1; i >= 0; i--) {
            if(flag[i] == true) break;
        }
        if(IsPalindrome(s, i, step-1)) {
            PartitionStep(s, step+1, flag);
        }
        flag[step] = false;
        PartitionStep(s, step+1, flag);
    }
    
    bool IsPalindrome(string s, int i, int j) {
        while(i < j) {
            if(s[i] != s[j]) return false;
            i++;
            j--;
        }
        return true;
    }
    
    void GenAnsItem(string s, bool *flag) {
        vector<string> item;
        item.clear();
        int i = 1;
        int before = 0;
        while(i <= s.length()) {
            if(flag[i] == true) {
                string tmp = "";
                for(int j = before; j < i; j++) {
                    tmp.push_back(s[j]);
                }
                item.push_back(tmp);
                before = i;
            }
            i++;
        }
        ans.push_back(item);
    }
};