题目链接：LeetCode 131. 分割回文串

题意：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

解题思路：

dfs算法的过程其实就是一棵递归树，所有的dfs算法的步骤大概有以下几步：

1. 找到中止条件：即递归树从根节点走到叶子节点时的返回条件，此时一般情况下已经遍历完了从根节点到叶子结点的一条路径，往往就是我们需要存下来的一种合法方案
2. 如果还没有走到底，那么我们需要对当前层的所有可能选择方案进行枚举，加入路径中，然后走向下一层
3. 在枚举过程中，有些情况下需要对不可能走到底的情况进行预判，如果已经知道这条路不可能到达我们想去的地方，那我们干嘛还要一条路走到黑呢，这就是我们常说的剪枝的过程
4. 当完成往下层的递归后，我们需要将当前层的选择状态进行清零，它下去之前是什么样子，我们现在就要让它恢复原状，也叫恢复现场。该过程就是回溯，目的是回到最初选择路口的起点，好再试试其他的路。

代码：

var (
    path []string  // 放已经回文的子串
    res  [][]string //存最终所有的路径
)
func partition(s string) [][]string {
    path, res = make([]string, 0), make([][]string, 0)
    dfs(s, 0)
    return res
}

func dfs(s string, start int) {
    if start == len(s) { // 如果起始位置等于s的大小，说明已经找到了一组分割方案了（中止条件）
        tmp := make([]string, len(path))
        copy(tmp, path)
        res = append(res, tmp)
        return 
    }
     
    for i := start; i < len(s); i++ { //从当前位置开始，一直到末尾，遍历所有的可能（枚举）
        str := s[start : i+1]  //当前子串
        if isPalindrome(str) {   //判断是否是回文子串（如果是，则进行下一次分割，不是直接返回了 --- **剪枝 **）
            path = append(path, str)  //如果是，就把他加到当前分割方案中
            dfs(s, i+1)         // 寻找i+1为起始位置的子串
            path = path[:len(path)-1]  // 回溯过程，弹出本次已经添加的子串 （恢复现场  --- 回溯 ）
        }
    }
}

func isPalindrome(s string) bool {

    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}