回溯法_回溯法时间复杂度

魏老师的回溯课堂（学生小小）

一、 回溯法技巧

1 认识回溯法

1.1 动态规划特点

 （i）回溯法作为递归算法的一个分支，通常动态规划是一种有智慧的暴力穷举，而回溯法则是简单粗暴的暴力穷举
 （ii）回溯算法的时间复杂度都很高，一般是次方，甚至指数时间复杂度。而动态规划的时间复杂度都比较低，是因为使用了状态转移方程消除了重叠子问题
 （iii）解决一个回溯问题，实际上就是遍历决策树的问题

1.2 回溯三要素

 （i）结束条件，达到决策底层，无法再进行决策
 （ii）路径(track)：已经做出的决策
 （iii）选择列表：当前可以做的决策
 （iv）剪枝条件：排除重复的元素

1.3 回溯算法框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        是否需要剪枝？？？
        做选择
        backtrack(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10
11

1.3.1 理解回溯法

 （i）回溯法的核心在内部的for循环，决策树其实是一棵N叉树，所以回溯法也是树的遍历

void traverse(TreeNode root) {
    for (TreeNode child : root.childern)
        // 前序遍历需要的操作
        traverse(child);
        // 后序遍历需要的操作
}
1
2
3
4
5
6

 （ii）backtrack函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，停止回溯
 （iii）确维护每个节点的属性：访问结点前做选择，将选择加入路径track中；访问节点后撤销选择，将选择从track移除
 （iv）回溯算法的重点是结束条件、先序应该做什么、回溯法的形参有什么(显然track路径一定有，问题形参也要有，还有,)，最后后序很简单，只需要弹出最后的元素即可
 （v）选择列表和剪枝：清楚当前的选择是什么，需不需要剪枝，也就是for循环循环变量的起点和终点很重要

2 基础问题

2.1 全排列 46

 （i）问题描述：输入不包含重复数字的数组，返回它的所有排列
 （ii）n个元素的全排列个数是$$n!$$，如下图，3个元素的全排列有$$3!=6$$个。因此全排列是阶乘时间复杂度问题，回溯法的时间复杂度都很高

2.1.1 问题思路

 （i）结束条件：

        当路径track长度等于数组nums长度，代表一条分支结束，将路径track存入结果中，如上图最左侧的分支(1->2->3)
1

 （ii）选择列表与剪枝条件

        1. 对于每一个结点而言，都有nums.length个选择
        2. 上图中的”ד代表剪枝，也就是本次递归不会考虑这些不合理的情况。比如第二层最左侧结点，已经选择了1结点，这时就应该剪枝结点1，因为排列没有重复，紧接着第三层中每个结点就会剪枝掉2个不合理的结点
        3. 因此for循环每次都需要遍历nums数组
        4. 如何排除不合法的情况，在java中track可以选择list，进而用contains()方法判断
1
2
3
4