回溯法及与深度搜索和递归概念的区别

1. 概念

回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

通常如果需要列出所有的结果的时候，就需要使用回溯法(backtracking)。当然通过暴力解法也是可以，但是暴力解法会浪费太多的时间和空间。两点区别

1. 回溯法会回头，把路径 pop 出来，而暴力解法是走所有的解

2. 回溯法会剪枝，比如通过某些 if 条件滑过某些路径，减少很多不必要走的路

1.1 识别回溯

判断回溯很简单，拿到一个问题，如果感觉不穷举一下就没法知道答案，那就可以开始回溯了。 一般回溯的问题有三种：

1. 有没有解

2. 求所有解

3. 求最优解

1.2 深度搜索与回溯法的区别

简单一点可以认为　回溯法 = 深度搜索 + 剪枝。一般大家用深度搜索时，或多或少会剪枝，因此深度搜索与回溯法没有什么不同，可以在它们之间画上一个等号。简单的可以认为二者等价。

深度搜索一般用递归(recursion)来实现，这样比较简洁。

深度搜索能够在候选答案生成到一半时，就进行判断，抛弃不满足要求的答案，所以深度搜索比暴力搜索法要快。

1.3 深度搜索与递归的区别

深度搜索经常用递归(recursion)来实现，二者常常同时出现。深度搜索，是逻辑意义上的算法，递归，是一种物理意义上的实现，它和迭代(iteration)是对应的。深度搜索，可以用递归来实现，也可以用栈来实现；而递归，一般总是用来实现深度搜索。可以说，递归一定是深度搜索，深度搜索不一定用递归。

通过图示表示上面所论述的各个概念的关系如下：

1.4 回溯三部曲

1. 回溯函数模板返回值以及参数

1. 回溯算法中函数返回值⼀般为void

2. 回溯算法需要的参数可不像⼆叉树递归的时候那么容易⼀次性确定下来，所以⼀般是先写逻辑，然后需要什么参数，就填什么参数

2. 回溯函数终⽌条件

1. 什么时候达到了终⽌条件，树中就可以看出，⼀般来说搜到叶⼦节点了，也就找到了满⾜条件的⼀条答案，把这个答案存放起来，并结束本层递归

3. 回溯搜索的遍历过程

1. 回溯法⼀般是在集合中递归搜索，集合的⼤⼩构成了树的宽度，递归的深度构成的树的深度

伪代码：

for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩） ) {
  处理节点;
  backtracking(路径，选择列表); // 递归
  回溯，撤销处理结果
}

For循环可以理解是横向遍历，backtracking（递归）就是纵向遍历

2. 实战

2.1 组合总和

力扣第39题：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

2.2 解题

这个题就是需要穷举出所有符合条件的答案，那么通过前面的讲述，我们就可以很容易想到用回溯法进行实现。

通过回溯三部曲，我们可以进行代码实现：

classSolution {
​
    privateList<List<Integer>>result=newArrayList();
​
​
​
    publicList<List<Integer>>combinationSum(int[] candidates, inttarget) {
​
        List<Integer>comb=newArrayList();
        call(candidates, 0, target, comb, 0);
        returnresult;
    }
​
    // 递归函数
    publicvoidcall(int[] candidates, intindex, inttarget, List<Integer>comb, intsum) {
        // 终止条件，需要兼容首次首次调用的情况（可能还有更优的判断方式）
        if (sum==target) {
            if (comb.size() !=0) {
                result.add(comb);
            }
            return;
        }
      // 已经存入list中的数据之和如果已经大于target的话，也可以作为终止条件
        if (sum>target) {
            return;
        }
      // 这里for循环代表递归的某个层级，即横向遍历
        for (inti=index; i<candidates.length; i++) {
            List<Integer>cp=newArrayList();
            cp.addAll(comb);
            cp.add(candidates[i]);
            call(candidates, i, target, cp, sum+candidates[i]);
        }
        
    }
}

参考：

https://zhuanlan.zhihu.com/p/65132408

https://bbs.huaweicloud.com/blogs/349853

《代码随想录》