回溯算法|78.子集

news/2024/5/20 19:28:26

力扣题目链接

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集,要放在终止添加的上面,否则会漏掉自己if (startIndex >= nums.size()) { // 终止条件可以不加return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

这题比较好理解啦~

思路

求子集问题和77.组合 (opens new window)和131.分割回文串 (opens new window)又不一样了。

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!

其实子集也是一种组合问题,因为它的集合是无序的,子集{1,2} 和 子集{2,1}是一样的。

那么既然是无序,取过的元素不会重复取,写回溯算法的时候,for就要从startIndex开始,而不是从0开始!

有同学问了,什么时候for可以从0开始呢?

求排列问题的时候,就要从0开始,因为集合是有序的,{1, 2} 和{2, 1}是两个集合,排列问题我们后续的文章就会讲到的。

以示例中nums = [1,2,3]为例把求子集抽象为树型结构,如下:

78.子集

从图中红线部分,可以看出遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合

#回溯三部曲

  • 递归函数参数

全局变量数组path为子集收集元素,二维数组result存放子集组合。(也可以放到递归函数参数里)

递归函数参数在上面讲到了,需要startIndex。

代码如下:

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {

递归终止条件

从图中可以看出:

78.子集

剩余集合为空的时候,就是叶子节点。

那么什么时候剩余集合为空呢?

就是startIndex已经大于数组的长度了,就终止了,因为没有元素可取了,代码如下:

if (startIndex >= nums.size()) {return;
}

其实可以不需要加终止条件,因为startIndex >= nums.size(),本层for循环本来也结束了

  • 单层搜索逻辑

求取子集问题,不需要任何剪枝!因为子集就是要遍历整棵树

那么单层递归逻辑代码如下:

for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);    // 子集收集元素backtracking(nums, i + 1);  // 注意从i+1开始,元素不重复取path.pop_back();            // 回溯
}

根据关于回溯算法,你该了解这些! (opens new window)给出的回溯算法模板:

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

自己的思路: 

其实我不太清楚空集它是如何保存的。

result.push_back(path); // 收集子集,要放在终止添加的上面,否则会漏掉自己

是这个吗?好像不是

好像也是的,一开始没有路径,直接push进去的就是空集

后面的就和之前几天写的代码差不多了,好理解~

 


https://www.xjx100.cn/news/3366605.html

相关文章

vue父组件值变化,子组件不刷新的问题(三种方案)

目录 1、在子组件使用 watch 监听 props传过来的值&#xff0c;如果发现改变&#xff0c;调用forceUpdate刷新视图。 2、父组件中声明一个布尔变量&#xff0c;数据发生变化后&#xff0c;切换一下变量状态&#xff0c;可刷新子组件视图。 3、数据发生变化后&#xff0c;在下…

笔记: JavaSE day15 笔记

第十五天课堂笔记 数组 可变长参数★★★ 方法 : 返回值类型 方法名(参数类型 参数名 , 参数类型 … 可变长参数名){}方法体 : 变长参数 相当于一个数组一个数组最多只能有一个可变长参数, 并放到列表的最后parameter : 方法参数 数组相关算法★★ 冒泡排序 由小到大: 从前…

代码随想录第29天|491.递增子序列 46.全排列 47.全排列 II

目录&#xff1a; 491.递增子序列 46.全排列 47.全排列 II 491.递增子序列 491. 非递减子序列 - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.com) 回溯算法精讲&#xff0c;树层去重与树枝去重 | LeetCode&#xff1a;491.递增子序列_哔哩哔哩_bili…

第二题:合法日期

题目描述 小蓝正在上小学&#xff0c;老师要求同学们在暑假每天记日记。可是小蓝整个暑假都在玩&#xff0c;直到最后一天才想起要记日记。于是小蓝赶紧编了一些日记交给老师。 没想到&#xff0c;日记很快就被老师发现了问题&#xff0c;原来小蓝记完 8 月 31 日的日记&…

Android源码笔记-输入事件(一)

这一节主要了解一下Android输入事件源码&#xff0c;Android输入系统的工作原理概括来说&#xff0c;就是监控/dev/input/下的所有设备节点&#xff0c;当某个节点有数据可读时&#xff0c;将数据读出并进行一系列的加工&#xff0c;然后在所有的窗口中寻找合适的事件接收者&am…

Solana 线下活动回顾|多方创新实践,引领 Solana“文艺复兴”新浪潮

Solana 作为在过去一年里实现突破式飞跃的头部公链&#xff0c;究竟是如何与 Web3 行业共振&#xff0c;带来全新的技术发展与生态亮点的呢&#xff1f;在 3 月 24 日刚结束的「TinTin Destination Moon」活动现场&#xff0c;来自 Solana 生态的的专家大咖和 Web3 行业的资深人…

演绎推理【科学推理】

演绎推理是集观察&#xff0c;实验&#xff0c;类比&#xff0c;联想&#xff0c;联想&#xff0c;经验归纳为一体的推理方法。 特点是有一般到特殊&#xff0c;有分析&#xff0c;综合&#xff0c;化归等解题策略。 正推是充分性&#xff0c; 反推是必要性。 小充分 …

谈谈你对 ES6 的理解

es6 是一个新的标准&#xff0c;它包含了许多新的语言特性和库&#xff0c;是 JS 最实质性的一次升级。 比如箭头函数、字符串模板、generators(生成器)、async/await、解构赋值、class等等&#xff0c;还有就是引入 module 模块的概念。 箭头函数可以让 this 指向固定化&…