回溯总结二：子集问题&排列问题&性能分析

78. 子集、90. 子集 II、491. 递增子序列_清榎的博客-CSDN博客

78是最基本的子集问题，90题在78的基础上进行了同层去重

两种去重方法，used数组标记 和 i>start

491.递增子序列就有点复杂了，树状图如下：

 

要注意它的去重方法。 

46. 全排列、47. 全排列 II_清榎的博客-CSDN博客

排列问题相比组合问题的不同在于次序需要考虑，因此表现在程序中就是每次开始都需要从头寻找 

对于排列问题的去重可以见 47.全排列Ⅱ，当然47题不仅可以树层去重也可以进行树枝上的去重，树的图如下：

但是树层去重效率更高，因为没有继续往下递归。

性能分析（来自carl）

子集问题分析：

• 时间复杂度：$O(n × 2^n)$，因为每一个元素的状态无外乎取与不取，所以时间复杂度为$O(2^n)$，构造每一组子集都需要填进数组，又有需要$O(n)$，最终时间复杂度：$O(n × 2^n)$。
• 空间复杂度：$O(n)$，递归深度为n，所以系统栈所用空间为$O(n)$，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$。

排列问题分析：

• 时间复杂度：$O(n!)$，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ..... 1 = n!。每个叶子节点都会有一个构造全排列填进数组的操作（对应的代码：result.push_back(path)），该操作的复杂度为$O(n)$。所以，最终时间复杂度为：n * n!，简化为$O(n!)$。
• 空间复杂度：$O(n)$，和子集问题同理。

组合问题分析：

• 时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
• 空间复杂度：$O(n)$，和子集问题同理。

一般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是一个概括吧！