分治、回溯算法
回溯:回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。 回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:
- 找到一个可能存在的正确的答案;
- 在尝试了所有可能的分步方法后宣告该问题没有答案。
在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。
分治、回溯的算法在本质上就是一种递归的状态。
22. 括号生成
50. Pow(x, n)
17. 电话号码的字母组合
78. 子集(全排列)
169. 多数元素
229. 求众数 II
面试题 08.12. 八皇后
51. N 皇后
52. N皇后 II