回溯算法

1. 递归和回溯的联系？
   递归是回溯的基础，实际上回溯只是在递归的基础上，加上回溯操作。因此递归和回溯是密不可分的。

2. 回溯算法有什么用？
   回溯本质上是暴力搜索算法，之所以需要回溯暴力搜索，是因为有一些问题仅仅依靠for循环是枚举不了答案。
   例如：组合、排列、字符串切割、棋盘问题、子集。这几个问题通过for循环是不能够枚举答案的。
   因此需要回溯来构造答案，根据一定的枚举规则在问题解空间里面搜索

3. 回溯算法的一些特点
   回溯算法必然可以使用一颗n叉树来表示。因为递归是回溯的基础，递归本身可以用树来表示，所以回溯也可以用树来表示。
   n叉树的深度就表示递归的深度，宽度表示枚举元素的个数。

4. 回溯的代码模板

void dfs(int u, 集合) {
    if (u == n) { // 如果解空间在n叉树的子节点，就要在这里收集答案。 例如组合 排列 棋盘
        // 收集答案
        return;
    }

    for (枚举集合元素) {
        处理元素,构造答案的过程  // 如果是子集问题 需要在这里收集答案
        dfs(u + 1 , 集合);  // 进入下一层递归
        回溯操作
    }
}

训练回溯算法

需要练习多一些相关的题目， 简单的先从全排列， 重复元素排列 ， 子集， 组合等基本题目开始。
回溯算法还涉及 剪枝。 当解空间过大，树中有一些分支是可以提前剪掉，从而加速搜索答案的过程。

相关题目

// 含重复的字符串排列
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

// 子集
https://leetcode-cn.com/problems/subsets-ii/

//组合 切割回文子串
// 子集
// 全排列
// 47. 全排列 II