7.4 回溯算法

[giscus[bot]]

7.4 回溯算法

回溯算法 1. 回溯算法简介 回溯算法（Backtracking）：一种能避免不必要搜索的穷举式的搜索算法。采用试错的思想，在搜索尝试过程中寻找问题的解，当探索到某一步时，发现原先的选择并不满足求解条件，或者还需要满足更多求解条件时，就退回一步（回溯）重新选择，这种走不通就退回再走的技术称为「回溯法」，而满足回溯条件的某个状态的点称为「回溯点」。 ...

https://algo.itcharge.cn/07_algorithm/07_04_backtracking_algorithm/

[WilsoEdwards]

5.1时间复杂度应该是2^n吧

[itcharge]

时间复杂度是 $O(n×2^n)$，因为总共有 $2^n$ 个状态，但是每一种状态都需要 $O(n)$ 的时间来构造子集。