回溯算法总结

最近跟着代码随想录的卡哥在刷回溯相关的算法题，在此推荐一下卡哥的视频以及官网。

带你学透回溯算法（理论篇）| 回溯法精讲！_哔哩哔哩_bilibili

卡哥在讲回溯算法的过程中给出我们一个大概的步骤去解决回溯算法。

第一步、先画出树形结构图，回溯的过程是一个深搜的过程，我们可以将找寻的过程画成一个树形结构图，再根据题目要求，判断在哪里收集结果。

第二步、构建回溯函数的参数及终止条件。

1.回溯函数通常是没有返回值的，参数的选择要取决于要利用哪些变量来得到最终的结果，如组合问题、子集问题及分割问题都要将原始数组传入，并且还需传入目前的索引位置。方便下一步回溯。

2.针对终止条件，就需要根据前面的树形结构图来判断，在子集问题中，需要收集的是树形结构图中的每个节点位置，但是在全排列问题中，需要收集的是叶子节点。针对不同的问题，想好不同的终止条件。

第三步、写每一层搜索的逻辑

在每一层搜索的过程中，要想好什么时候可以将结果放入到结果集中，以及如何排除不必要的元素。最重要的是，单层递归结束后，一定要还原回原本的样子。以便后续遍历过程中不会受影响。

好，我们已经知道了如何应对回溯类型的题目，下面是一个简单的模板，可以应用于一些组合、分割、全排列以及子集问题

var (
	result [][]int   //这存放的是最终要返回去的结果，相当于每层结果都放入到result 中
	path   []int     //这存放的是每一层元素的组合，要在合适的时候将其加入到result
)
 
func backfunction(nums []int) [][]int {
    //先初始化
	result, path = make([][]int, 0), make([]int, 0)
	//调用递归函数，传入参数
    backtracking(nums, 0)
    return result
}
//递归函数
func backtracking(nums []int, start int) {
    //确定终止条件
	if start > len(nums) {
       //得到中间数组，将path的值赋予tmp,并加入最终结果集
	   tmp := make([]int, len(path))
	   copy(tmp, path)
	   result = append(result, tmp)
       return
    }
    //单层搜索逻辑
	for i := start; i < len(nums); i++ {
        搜索逻辑……
 
	    //将结果添加到每一层的结果中
        path = append(path, nums[i])
        //进行下一层递归
		backtracking(nums, i+1)
        //递归结束后，要将结果恢复到没递归前的样子
		path = path[:len(path)-1]
	}
}

大致的模板就是这样，具体的涉及到去重，还需要加上一些条件。例如可以先将数组排序，然后如果前后两个元素值相等，那么后一个跳过，不进行递归。而且还要根据题目条件来判断是是当前层不能有重复元素还是，不同层不能有重复元素。根据这个判断代码如何写。