回溯算法时间复杂度分析

子集问题分析：

时间复杂度：O(n x 2^n)。因为每一个元素的状态无外乎取与不取，一共2^n 种状态，每种状态都需要O(n)的构造时间，最终时间复杂度为O(n x 2^n) 。

空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为 O(n) 。

排列问题分析：

时间复杂度：： O(n x n!) 。因为一共n! 种排列，每种排列都需要O(n)的构造时间，最终时间复杂度为 O(n x n!) 。

空间复杂度： O(n)，递归深度为n，所以系统栈所用空间为O(n)。

组合问题分析：

**时间复杂度：**O(C(下n，上k) x k) ，总共有 C(下n，上k) 种组合，每种组合需要O(n)的时间复杂度。另一方面，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度 O(2 x 2^n) 。

空间复杂度：O(n) ，递归深度为n，所以系统栈所用空间为 O(n) 。

N皇后问题分析

时间复杂度： O(N!) ，其中 N 是皇后数量，由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择，第二个皇后最多有 N-1列可以选择…。

空间复杂度：O(N) ，递归深度为n，所以系统栈所用空间为 O(N) 。

解数独问题分析

时间复杂度： O(9^m) ，m是’.'的数目。

空间复杂度： O(n^2) ，n是数独盘子的大小，递归的深度是 n^2 。