给定一个字符串，切割字符串，这样每个子字符串是一个回文字符串。

要找出所有可能的组合。

办法：暴力搜索+回溯

class Solution {

public:

	int *b,n;

	vector<vector<string> >ans;

	void dfs(int id,string &s,int len){

		if(id>=n){

			if(len>0){

				vector<string>vt;

				vt.push_back(s.substr(0,b[0]+1));

				for(int i=1;i<len;++i){

					vt.push_back(s.substr(b[i-1]+1,b[i]-b[i-1]));

				}

				ans.push_back(vt);

			}

			return;

		}

		int j,k;

		b[len]=id;

		dfs(id+1,s,len+1);

		for(j=id+1;j<n;++j){

			for(k=0;id+k<j-k&&s[id+k]==s[j-k];++k);

			if(id+k>=j-k){

				b[len]=j;

				dfs(j+1,s,len+1);

			}

		}

	}

	vector<vector<string> > partition(string s) {

		n=s.size();

		if(n==0)return ans;

        if(n==1){

            vector<string>vt;

            vt.push_back(s);

			ans.push_back(vt);

			return ans;

		}

		b=new int[n];

		dfs(0,s,0);

		return ans;

    }

};