:::info 回溯是递归的产物，有递归一般就会产生回溯，比如之前的二叉树中求路径的题 :::

基本模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

:::tips

• 回溯可以考虑成二叉树的遍历，每一层是有那些选项，每一个树枝是有那些选项
• 子集、组合、排列问题的区别：可行的path是什么样的，去重在哪里去；
• 去重可以分成：对当前层内去重&对当前枝上去重；对当前层内的去重可以在for循环体内做，枝内去重可以用一个set跟随path去记录path里的值是否以及用了，并且随着回溯增改；

• 回溯函数是否需要返回值一般看情况：

  • 如果需要所有的解，那么一般不需要返回值；
  • 如果需要一个解，那么一般可能需要返回值； :::

    可解问题

• 组合问题：N个数里面按一定规则找出k个数的集合

• 排列问题：N个数按一定规则全排列，有几种排列方式
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 棋盘问题：N皇后，解数独等等