代码随想录算法训练营第24天 | 回溯算法理论基础 77.组合

发布时间:2024年01月23日

理论基础

回溯是递归的副产品,有递归就会有回溯。回溯算法的本质就是穷举,因此效率并不高,顶多采用剪枝的方式使之高效一些
可以解决的问题:

  1. 组合问题:N个数按一定规则找出k个数的集合
  2. 切割问题:一个字符串按一定规则有几种切割方式
  3. 子集问题:一个N个数的集合里有多少符合条件的子集
  4. 排列问题:N个数按一定规则有几种排列方式
  5. 棋盘问题:N皇后、解数独等

回溯算法解决的问题都可以抽象为树形结构。要解决的问题都可以看做在集合中找子集,集合的大小构成了树的宽度,递归的深度就是树高。抽象如下:Alt
回溯函数其实就是递归函数,模板其实与递归也差不多。

void backtracking(参数){
	if(终止条件){
		存放结果;
		return;
	}
	for(选择的元素 : 本层集合中元素(孩子节点的数目就是集合的大小)){
		处理节点;
		backtracking(路径, 选择列表);
		回溯操作,撤销处理结果;
	}
}

组合

Alt
从 [1, n] 中选 k 个数进行组合,将这个穷举过程抽象为 n 叉树的遍历,每一层的可选数目等于当前遍历集合的大小。

class Solution{
public:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(int startIndex, int n, int k){
		if(path.size() == k){
			result.push_back(path);
			return;
		}
		for(int i = startIndex; i <= n; i++){  // 从startIndex开始,下一次递归+1
			path.push_back(i);
			backtracking(i + 1, n, k);  // 递归
			path.pop_back();  // 回溯
		}
	}
	vector<vector<int>> combine(int n, int k){
		backtracking(1, n, k);
		return result;
	}
};

剪枝操作

如果是 n = 4, k = 4 的话,那么第一层 for 循环的时候,从元素 2 开始的遍历都没有意义了,当递归到下一层时从元素 3 开始的遍历都没有意义了。当前递归层中还要添加的元素数目为 k - path.size(),同时要注意从 n - (k - path.size() - 1) 到 n 才是 k - path.size() 个元素。

class Solution{
public:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(int startIndex, int n, int k){
		if(path.size() == k){
			result.push_back(path);
			return;
		}
		for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){
			path.push_back(i);
			backtracking(i + 1, n, k);
			path.pop_back();
		}
	}
	vector<vector<int>> combine(int n, int k){
		backtracking(1, n, k);
		return result;
	}
};
文章来源:https://blog.csdn.net/qq_44173169/article/details/135706027
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。