回溯理论基础

回溯法（回溯搜索法），是一种搜索的方式。

只要有递归就会有回溯。

因此，回溯函数也就是递归函数，指的都是一个函数。

回溯的本质是穷举。

回溯法解决的问题

  • 组合问题：N个数里面按一定规则找出k个数的集合。
  • 切割问题：一个字符串按一定规则有几种切割方式。
  • 子集问题：一个N个数的集合里有多少个符合条件的子集。
  • 排列问题：N个数按一定规则全排列，有几种排列方式。
  • 棋盘问题：N皇后，解数独等等

排列？组合？

组合是不强调元素顺序的，排列是强调元素顺序的。

组合无序，排列有序

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构。

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度都构成了树的深度。

回溯三部曲

  • 回溯函数模板返回值以及参数

名字：backtracking

返回值：一般为void

参数：一般先写逻辑，然后需要什么参数就填什么参数

  • 终止条件

一般来说搜到叶子节点也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

  • 回溯搜索的遍历过程

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度

1
2
3
4
5
for(选择：本层集合中的元素（树种节点孩子的数量就是集合的大小）){
	处理节点；
	backtracking（路径，选择列表）；//递归
	回溯，撤销处理结果；
}

for循环可以理解为横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

因此，回溯算法模板框架如下：

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数){
	if(终止条件){
		存放结果；
		return;
	}
	for(选择：本层集合中元素（树种节点孩子的数量就是集合的大小）){
		处理节点；
		backtracking(路径，选择列表);//递归
		回溯，撤销处理结果；
	}
}

77.组合

文章：2. 组合问题

题目：77. 组合

把组合问题抽象为树形结构。每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。不难发现，n相当于树的宽度，k相当于树的深度。接下来我们需要获取结果集，图中每次搜索到了叶子节点，我们就找到了一个结果。

回溯三部曲：

  • 递归函数的返回值以及参数

    定义两个全局变量，一个用来存放单一结果，一个用来存放符合条件结果的集合。

  • Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return list;
    }
    public void backtracking(int n,int k,int start){
        if(path.size() == k){
            list.add(new ArrayList<>(path));
            return; 
        }
        for(int i = start ;i <= n ; i++ ){
            if(n-i+1 < k - path.size())break;
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }

}
  • Go实现

剪枝法：

1
2
3
if n-i+1 < k - len(tmp){
                break
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func combine(n int, k int) [][]int {
    res:=make([][]int,0)
    tmp := make([]int,0)
    //startIndex 每次回溯for循环用的初始索引
    var backtracking func(n,k,startIndex int)
    backtracking = func(n,k,startIndex int){
        if len(tmp) == k{
            temp := make([]int,k)
            copy(temp,tmp)
            res = append(res,temp)
                        //path = []int 回溯不在这里进行
            return 
        }
        for i:=startIndex;i<=n;i++{
            if n -i +1 < k-len(path){  //剪枝
                break
            }
//在当前位置 i 到末尾的剩余元素个数不足以凑齐剩余的组合元素个数 k - len(path)
            tmp = append(tmp,i)
            backtracking(n,k,i+1)
            tmp = tmp[:len(tmp)-1]
        }
    }
    backtracking(n,k,1)
    return res
}

【算法总结】

  • 组合：使用回溯+剪枝的方法，确定好每次遍历的初始索引，然后递归回溯回去添加即可。

【语言总结】

  • Java

    使用LinkedList来进行动态数组的添加，然后通过new ArrayList<>(list)转化为ArrayList的其中一个集合。