[Vssue]回溯总结.md

[youngyangyang04]

https://www.programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

[Du1in9]

组合问题

时间复杂度：O(2^n)，组合问题就是特殊的子集问题，所以最坏情况不会超过子集问题的时间复杂度。空间复杂度：O(n)。

子集问题

时间复杂度：O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为 O(2^n)。空间复杂度：O(n)。

排列问题

时间复杂度：O(n!)，第一层 n 个分支，第二层 n-1 个分支， ... ，一直到叶子节点一共就是 n! 。空间复杂度：O(n)。

N皇后问题

时间复杂度：O(n!) ，直觉上是 O(n^n)，但皇后之间不能同列所以有剪枝，最差情况是 O(n!)。空间复杂度：O(n)。

解数独问题

时间复杂度：O(9^m)，其中 m 是 '.' 的数目。空间复杂度：O(n^2)，递归深度为 n^2。