力扣：131. 分割回文串

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 

回文串

 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        back(s,0);
        return ans;
    }
    public void back(String s,int start){
        if(start==s.length()){//当此起始点分完了
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i = start;i < s.length();i++){//从起始点开始，依次向右分割
            if(isPalindrome(start,i,s)){
                path.add(s.substring(start,i+1));//因为substring是左闭右开，所以要加一
            }else{
                continue;//不是回文则继续分割
            }
            back(s,i+1);//分割起始点右移
            path.remove(path.size()-1);
        }
    }
    public boolean isPalindrome(int start,int end,String s){//判断是否为回文
        while(start<end){
            if(s.charAt(start)==s.charAt(end)){
                start++;end--;
            }else{
                return false;
            }
        }
        return true;
    }
}