Leetcode回溯算法小结

这两周刷了好多回溯算法，应该输出一点东西总结一下。

回溯算法介绍

回溯法解决的问题：要了解回溯算法，首先我们要知道回溯算法用于解决什么问题，当遇到越来越多层次的嵌套循环，显然通过自己写一层一层for循环嵌套不是个办法，所以就需要通过递归嵌套for循环来实现多层for循环，回溯的本质就是递归，

回溯的过程：回溯的过程就是相当于就是深度优先搜索树的过程，树的宽度就是for循环的大小，树的深度就是递归的深度。

回溯的问题分类：组合 集合 切割 排列 N皇后 数独

• 组合问题：N个数里面按一定规则找出k个数的集合
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 切割问题：一个字符串按一定规则有几种切割方式（其实就是求无间断的组合，组合的大小无所谓，只要满足题目条件）
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 棋盘问题：N皇后，解数独等等

img、

回溯算法的模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

提出问题

1. 什么时候收集结果集
2. 什么时候要startIndex,什么时候不要
3. 什么时候剪枝
4. 什么时候需要used数组去重，什么是树枝去重和数层去重

题目代码我就不贴了，大神的题解比我的好看一百倍