1.上期参考代码
class Solution {
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;
}
void dfs(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
高中，我们学集合的时候知道，一个集合的子集个数为 2^n 个。这个 2^n 怎么来的？
在一个元素对于集合来说，只有两种情况：存在或者不存在。
对于每一个元素进行存在或者不存在的划分，我们可以得出以下的决策图：
我们发现决策树的结果完全符合我们的期望，所以这就是一个好的决策树。
有了决策树，根据其写代码就方便多啦~
根据决策树，我们得出需要
两个全局变量：
- 上一级已经存放了的元素–>变量path（也可以设置成函数参数，避免返回现场操作）
- 存放 path 的二维数组用于返回所有结果–>ret
父子层信息传递需要：
- 数组–>nums
- 这一层是对数组中第几个元素进行判断–>pos
代码逻辑
观察我们想要的结果，都是在叶子结点，很明显，
出口在叶子节点
重复子问题：对于每个元素根据其是否存在，分两种情况讨论 子问题干啥：存在则将其放入 path 中，进入下一层，不存在啥也不做，进入下一层
4.2 决策树 2
我们也可以根据，子集中元素的个数，来画决策图：
这张决策图同样需要全局变量 path 和 ret，它也能获得我们想要的结果，也是一个好的决策图。
由于子集中没有排序，只有组合，所以我们要对重复的子集进行剪枝，如图中所示：按照顺序来给 path 添加元素。
提示： 结合 for 循环，不用设置 return 出口，for 循环能实现数组递归中的按下标顺序添加元素，进行剪枝，出口的本质是：'没有可选择元素'。
不知道大家有没有发现，数组往往是多叉树的遍历，多叉树的遍历必然用到 for，而 for 往往是遍历到最后，也就不需要设置 return 出口~
