回溯算法
<p>回溯算法常用来解决以下问题：</p>
<ol>
<li>排列问题</li>
<li>组合问题</li>
<li>切割问题：一个字符串按照某种规则有几种切割方式</li>
<li>子集问题</li>
<li>棋盘问题</li>
</ol>
<p>套路框架就是遍历决策树
其核心就是 for 循环里面的递归，在递归调用之前做<strong>选择</strong>，在递归调用之后<strong>撤销选择</strong></p>
<pre><code>result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
</code></pre>
<p>做选择和撤销选择的详解</p>
<pre><code>for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表</code></pre>
<p>不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。<strong>这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。</strong>
注意，add的时候要new，不然是引用，会出问题</p>
<pre><code> private static void backtrack(List<Integer> temp, int[] nums) {
if (temp.size() == nums.length) {
// 这里注意要new
result.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (temp.contains(nums[i])) {
continue;
}
temp.add(nums[i]);
backtrack(temp, nums);
temp.remove(temp.size()-1);
}
}</code></pre>
<p><a href="https://zhuanlan.zhihu.com/p/93530380" title="参考文章">参考文章</a></p>