一、参考资料
理论基础
视频讲解:https://www.bilibili.com/video/BV1cy4y167mM
组合
题目链接/文章讲解:https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
视频讲解:https://www.bilibili.com/video/BV1ti4y1L7cv
剪枝操作:https://www.bilibili.com/video/BV1wi4y157er
二、理论基础
回溯的遍历过程如图:
三、LeetCode77. 组合
https://leetcode.cn/problems/combinations/description/
组合问题抽象
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1:
输入:n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2:
输入:n = 1, k = 1 输出:[[1]]
提示:
1 <= n <= 20
1 <= k <= n
- class Solution {
- private:
- vector<vector<int>> res; // 定义一个结果集数组
- vector<int> path; // 定义路径,用来存放符合条件的结果
-
- void backtracking (int n, int k, int startIndex) {
- if (path.size() == k) {
- res.push_back(path);
- return ;
- }
- for (int i = startIndex; i <= n; i++) {
- path.push_back(i); // 处理节点
- backtracking(n, k, i + 1); // 递归
- path.pop_back(); // 回溯,撤销处理的节点
- }
- }
-
- public:
- vector<vector<int>> combine(int n, int k) {
- backtracking(n, k, 1);
- return res;
- }
- };
我写的:
- class Solution {
- private:
- vector<int> path; // 用于存放符合条件的路径
- vector<vector<int>> res; // 用于存放结果集
-
- void backtracking(int n, int k, int startIndex) {
- // startIndex是为了防止重复组合(排列才和元素顺序有关)
- if (path.size() == k) {
- res.push_back(path);
- return ;
- }
- for (int i = startIndex; i <= n; i++) {
- path.push_back(i);
- backtracking(n, k, i + 1);
- path.pop_back();
- }
- }
- public:
- vector<vector<int>> combine(int n, int k) {
- backtracking(n, k, 1);
- return res;
- }
- };
剪枝操作:【看了两三遍,这个剪枝的条件有点点绕的】
图中每一个节点(图中为矩形),就代表本层的一个for循环,那么每一层的for循环从第二个数开始遍历的话,都没有意义,都是无效遍历。
所以,可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了。
注意代码中i,就是for循环里选择的起始位置。
for (int i = startIndex; i <= n; i++) {
接下来看一下优化过程如下:
已经选择的元素个数:path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历
为什么有个+1呢,因为包括起始位置,我们要是一个左闭的集合。
举个例子,n = 4,k = 3, 目前已经选取的元素为0(path.size为0),n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的,可以是组合[2, 3, 4]。
- class Solution {
- // 剪枝
- private:
- vector<vector<int>> res;
- vector<int> path;
- void backtracking(int n, int k, int startIndex) {
- if (path.size() == k) {
- res.push_back(path);
- return ;
- }
- for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
- path.push_back(i);
- backtracking(n, k, i + 1);
- path.pop_back();
- }
- }
- public:
- vector<vector<int>> combine(int n, int k) {
- backtracking(n, k, 1);
- return res;
- }
- };
今日总结:
有新的任务了,往后刷题可真就是海绵里挤水,时间变得更加宝贵==
学到兴致处时常感慨,时间过得太快了,想学的都学不完。
关于回溯:
在二叉树的基础上,理解还行,就是剪枝的条件有一点点没懂,看讲解能明白,自己想不一定写出来
另外在组合问题上,需要注意它不需要考虑元素的顺序,所以代码中startIndex的出现,就是标记N叉树下一层所需要选择的起始位置,每次都在前一层的基础上加1。
标签:int,res,随想录,back,77,算法,vector,path,backtracking From: https://www.cnblogs.com/ucaszym/p/17099955.html