Day 24 第七章 回溯算法part01

• 今日内容：
  • ● 理论基础
  • ● 77. 组合

理论基础

• 其实在讲解二叉树的时候，就给大家介绍过回溯，这次正式开启回溯算法，大家可以先看视频，对回溯算法有一个整体的了解。
• 视频讲解：https://www.bilibili.com/video/BV1cy4y167mM
• 文章讲解：https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

什么是回溯

程序在运行过程中分成了多个阶段
通过某些手段将数据恢复到之前的某一阶段，就称之为回溯
手段包括：1. 方法栈；2. 自定义栈

使用原因 & 解决的问题

回溯和递归是相辅相成的，只要有递归就会有回溯，回溯算法一般是在递归的下面
说到回溯函数其实就是递归函数
回溯法是一个纯暴力搜索，有些问题能纯暴力搜索出来就不错了

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

如何理解回溯法

所有回溯法都可以抽象成一个树形结构n叉树

树的宽度就是回溯法处理时集合的大小（利用for循环）
树的深度就是递归的深度（递归）
如图：

//回溯算法参数一般很难一开始就确定，需要啥就放啥
void backtracking(参数){
	if(终止条件){
		//收集结果
		return;
	}
	//单层搜索逻辑
	for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){
		//处理节点
		backtracking(路径， 选择列表);//递归函数
		//回溯操作，撤销处理结果
	}return;
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

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

77. 组合

• 对着 在 回溯算法理论基础 给出的 代码模板，来做本题组合问题，大家就会发现 写回溯算法套路。
• 在回溯算法解决实际问题的过程中，大家会有各种疑问，先看视频介绍，基本可以解决大家的疑惑。
• 本题关于剪枝操作是大家要理解的重点，因为后面很多回溯算法解决的题目，都是这个剪枝套路。
• 题目链接：https://leetcode.cn/problems/combinations/
• 视频讲解：https://www.bilibili.com/video/BV1ti4y1L7cv
  • 剪枝操作：https://www.bilibili.com/video/BV1wi4y157er
• 文章讲解：https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html

思路

与排列的思路一样，只不过是要设定一个start参数表示起始处理数字
这样就不用重复组合

剪枝

当剩余数字个数小于需要组合的数字个数时，就不需要再遍历了

代码

public static List<List<Integer>> combine(int n, int k) {
	List<List<Integer>> res = new ArrayList<>();
	dfs(1, n, k, new LinkedList<>(), res);
	return res;
}
//start：起始处理数字
public static void dfs(int start, int n, int k, LinkedList<Integer> stack, List<List<Integer>> res){
	if(stack.size() == k){
		res.add(new ArrayList<>(stack));
		return;
	}
	for (int i = start; i <= n; i++) {
		//❗剪枝操作
		// k - stack.size()：表示当前缺失的数字个数
		// n - i + 1：表示还剩几个备用数字
		if(n - i + 1 < k - stack.size()){
			continue;
		}
		stack.push(i);
		dfs(i + 1, n, k, stack, res);
		stack.pop();    //回溯
	}
}