回溯法小结

回溯法基本思想

参考文章：回溯法

首先我们要明确的是回溯法使用的场景，从我个人角度来看，回溯法和没有做任何优化的递归是一样的（或者说回溯法本身就是递归），都是属于暴力搜索的一种方式，但是有些时候我们难以区分回溯法和DP的区别，在第二小节我们详细解释。

解决一个回溯问题，其实就是遍历所有可能的情况，在需要记录的时候对解决方案进行记录，在发现当前方案不符合预期的时候返回遍历下一种方案，其最经典的应用有：求子集合、全排列以及组合问题。

伪代码框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，这里看似简单，却有很多天坑。回溯法有很多难题，后面遇到了会一一记录，而且面试考察也很多，因为回溯法经常可以和BFS、DFS一起考察。

回溯法与DP的使用区别

那么回溯法的难点在哪里呢？其实有很多小tips，例如LeetCode 377. Combination Sum IV，明明前三道combination都是在用回溯法，为什么到了第四题就用DP而不是回溯法了呢？再比如说为什么求subset的时候就不需要sort，而有些时候就需要sort呢？

我们这里先来看一下回溯法解决的问题和DP解决问题最大的不同

类目	回溯法	DP
解决问题类型	通常是求出给定条件的集合，注意，是最终的详细的解，而不是个数。	一般是求某个值，例如说最大值，最小值，或者XXX的个数，一般情况下不会给出额外的限定条件，因为DP是要写递推式的，有额外条件不方便写出普适的递推式。

这么看起来感觉比较抽象，我们来举个例子，LeetCode 39. Combination Sum和LeetCode 377. Combination Sum IV。

注意，以下分析仅针对39和337，所谓的不同的解就用DP之类的仅针对该题目，具体问题具体分析，这里只是举例看二者的区别

这里不再赘述题目。39题和377题最大的不同点在于39题可以重复，而337不行，什么意思呢？例如[1,3]和[3,1]在39题里是同一个解，而337题里是不同的解。

那么为什么不同的解就可以用DP而不能用回溯呢？我们要注意，不是说不能用回溯，只是说DP更快。因为回溯其实是暴力搜索的一种，而DP是对暴力搜索的优化，因此对这道题而言，能用DP就自然也能用回溯（这里存在遍历选项的问题因此可以用回溯，并不是所有DP都能用回溯，要注意这里是必要不充分条件）。

将39题的递归调用backtracking那块的代码，将i变换成0就是变成找出所有解了，就会将[1,3]和[3,1]当做不同解。从0开始递归找全局组合方式。

例如：给出[1,2,3]，我们的target是4，那么我们使用dp的时候，dp[4 - 1]和dp[4 - 3]我们都会去计算，因为我们不关心dp[3]和dp[1]是怎么来的，我们可以任意组合数字。

当我们使用回溯法的时候需要先对数组进行排序，然后遍历的时候只能向后遍历（包含当前节点），例如说我们到了1，我们可以从[1,2,3]中找可以组合成为3的组合；再或者我们到了2，我们就不能回去找1，就只能从[2,3]里找出所有可以组合为2的可能。这样保证了不重复

回溯法需要注意的点

什么时候回溯需要sort，而什么时候不要？

当我们原始数组里有重复数字（包括数字不重复可以重复使用）且需要不重复的解的时候需要sort。多看看下面的例子自行体会~

需要sort的例子有：LeetCode 39. Combination Sum
LeetCode 40. Combination Sum II
LeetCode 90. Subsets II

不需要sort的例子有：LeetCode 377. Combination Sum IV
LeetCode 78. Subsets

当给出的数组中存在重复数字怎么办？如何避免重复解

在循环选项之前加上这么一个if判断即可，例题：

LeetCode 40. Combination Sum II
LeetCode 90. Subsets II

for (int i = start; i < nums.length; i++) {
    if (i > start && nums[i] == nums[i - 1]) {
        continue;
    }
}