dfs专题8——子集
🔥近津薪荼： [个人主页]🎬个人专栏： 《近津薪荼的算法日迹》《Linux操作系统及网络基础知识分享》《c++基础知识详解》《c语言基础知识详解》✨不要物化，矮化，弱化，钝化自己，保持锋芒，不要停止学习这个世界上只有两个人真正在注意着你八岁的你，和八十岁的你，他们此刻正在注视着你，一个希望你 勇敢开始，一个希望你 不留遗憾
1.上期参考代码
classSolution{ vector<vector<int>>ret; vector<int>path; vector<bool>check=vector<bool>(6,false);public: vector<vector<int>>permute(vector<int>& nums){dfs(nums);return ret;}voiddfs(vector<int>& nums){if(path.size()==nums.size()){ ret.push_back(path);return;}for(int i=0;i<nums.size();i++){if(check[i]==false){ path.push_back(nums[i]); check[i]=true;dfs(nums);//回溯 check[i]=false; path.pop_back();}}}};2.本期知识点导图
3.本期要讲解的题目是
子集
要点：
- nums元素各异
- 要返回空集
4.解题
本题我们可以画出两种决策树
4.1决策树1
高中，我们学集合的时候知道，一个集合的子集个数为2n个，这个2n怎么来的？
在一个元素对于集合来说，只有两种情况：存在或者不存在
对于每一个元素进行存在或者不存正在的划分，我们可以得出以下的决策图：
我们发现决策树的结果完全符合我们的期望，所以这就是一个好的决策树。
有了决策树，根据其写代码就方便多啦~
根据决策树，我们得出需要
两个全局变量：
- 上一级已经存放了的元素–>变量path（也可以设置成函数参数，避免返回现场操作）
- 存放path的二维数组用于返回所有结果–>ret
父子层信息传递需要：
- 数组–>nums
- 这一层是对数组中第几个元素进行判断–>pos
代码逻辑
观察我们想要的结果，都是在叶子结点，很明显，
出口在叶子节点
重复子问题：对于每个元素根据其是否存在，分两种情况讨论
子问题干啥：存在则将其放入path中，进入下一层，不存在啥也不做，进入下一层
4.2决策树2
我们也可以根据，子集中元素的个数，来画决策图：
这张决策图同样需要全局变量path和ret，它也能获得我们想要的结果，也是一个好的决策图。
由于子集种没有排序，只有组合，所以我们要对重复的子集进行剪枝，如图中所示：按照顺序来给path添加元素
提示:
结合for循环，不用设置return出口，for循环能实现数组递归中的按下标顺序添加元素，进行剪枝，出口的本质是：“没有可选择元素”
不知道大家有没有发现，数组往往是多叉树的遍历，多叉树的遍历必然用到for，而for往往是遍历到最后，也就不需要设置return出口~
5.下期要讲解的题目是：
找出所有子集的异或总和再求和
6.嗟食
如果小编写的内容对佬有帮助，还请大佬点点三连加关注哦
佬的支持就是我前进的最大动力~
期待与佬的再次相遇~
