回溯算法

Posted by 渐行渐远 on Monday, November 29, 2021 共589字

遇到计算排列或者组合的问题，总是可以通过回溯的思想来解决。回溯的处理思路，就是遇到了岔路口，按照顺序依次去走每一个小路，当前的小路走不通时，重新回到上一个岔路口，记录走另一条没有走的路。

可能会有多个岔路，从数据结构的角度去分析，就是一个多叉树。而不停的回溯过程，就等价于多叉树的编历操作。二叉树的编历都是使用递归来实现，回溯算法一般使用的是中序编历：左节点-根节点-右节点

回溯算法

回溯算法的有写比较重要的点，我们依次来说明

构造一个树的结构

将问题抽象成一个树的遍历结构是根本

递归的退出条件

递归的退出条件，递归的退出条件肯定要在递归函数被调用之前判断，如果放到了递归函数调用之后，那绝对会导致栈溢出。这个退出的条件多种多样，我们可以通过控制递归的深度来确定是否要退出、或者遇到某个重复值执行退出。

递归中状态的更新和回退

在回溯的过程中，无可避免的会涉及到状态的回退。如果我们使用固定的空间来保存从根节点到叶子节点的一条路径，我们首先遍历做子树，当左子树遍历完成之后，我们开始遍历右子树之前，需要清空固定空间中的左子树节点。

有时候还要配合上去重过滤，也是状态的更新和回退。下面突出的两行就是状态的更新和回退

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 回溯所有遇到的情况
func find(candidates []int, target int, start int, temp []int) {

    for i := start; i < len(candidates); i++ {
        
        less := target - candidates[i]
        if less < 0 {
            continue
        }

        temp = append(temp, candidates[i])
        if less == 0 {
            gloablResult = append(gloablResult, append([]int{}, temp...))
        } else {
            find(candidates, target - candidates[i], i, temp)
        }
        
        temp = temp[:len(temp)-1]
    }
}