主要是我自己刷题的一些记录过程。如果有错可以指出哦,大家一起进步。
转载代码随想录
原文链接:
代码随想录
leetcode链接:78.子集
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
求子集问题和77.组合和131.分割回文串又不一样了。
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!
其实子集也是一种组合问题,因为它的集合是无序的,子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序,取过的元素不会重复取,写回溯算法的时候,for就要从startIndex开始,而不是从0开始!
有同学问了,什么时候for可以从0开始呢?
求排列问题的时候,就要从0开始,因为集合是有序的,{1, 2} 和{2, 1}是两个集合,排列问题我们后续的文章就会讲到的。
以示例中nums = [1,2,3]为例把求子集抽象为树型结构,如下:
从图中红线部分,可以看出遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合。
全局变量数组path为子集收集元素,二维数组result存放子集组合。(也可以放到递归函数参数里)
递归函数参数在上面讲到了,需要startIndex。
代码如下:
vector> result;
vector path;
void backtracking(vector& nums, int startIndex) {
从图中可以看出:
剩余集合为空的时候,就是叶子节点。
那么什么时候剩余集合为空呢?
就是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(); // 回溯
}
根据回溯算法模板:
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}
可以写出如下回溯算法C++代码:
class Solution {
private:vector> result;vector path;void backtracking(vector& 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> subsets(vector& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};
在注释中,可以发现可以不写终止条件,因为本来我们就要遍历整棵树。
有的同学可能担心不写终止条件会不会无限递归?
并不会,因为每次递归的下一层就是从i+1开始的。
//2.用位运算
class Solution {
public:vector> subsets(vector& nums) {vector>result;vectorpath;for (int i = 0; i < 1 << nums.size(); ++i) {path.clear();for (int j = 0; j < nums.size(); ++j) {if (i & 1 << j) {path.push_back(nums[j]);}}result.push_back(path);}return result;}
};class Solution {vector>result;vectorpath;void dfs(vector& nums, int startIndex) {result.push_back(path); //第一次来就是把空数组放进去for (int i = startIndex; i < nums.size(); ++i) {path.push_back(nums[i]);dfs(nums, i+1);path.pop_back();}return;}
public:vector> subsets(vector& nums) {dfs(nums, 0);return result;}
};
上一篇:数据安全-分类分级 调研分析报告