前言
回溯章节第9篇。记录 七十八【90.子集II】
一、题目阅读
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
二、尝试实现
分析题目，确定方法
- 题目明显告诉这是求子集。学过记录 七十五【78.子集】如何求子集。这是用回溯方法解决的。
- 但是本题的集合中有重复的元素，肯定要去重。去重的逻辑记录 六十七【40.组合总和II】中学过“树层去重”和“树枝去重”的概念。
- 所以本题结合两个方法的要点，即可解决。
思路
- 回溯需要确定一个树形结构。集合有重复元素，所以用used数组来记录该元素有没有被使用过。蓝色节点是要搜集的节点。去重的逻辑和记录 六十七【40.组合总和II】一致，是“树层去重”。
- 确定递归函数返回值：用全局变量vector<vector> result;放结果，所以返回值是void。
- 确定递归函数参数：
- int startindex。记录从哪个下标开始选。
- vector< bool>& used代表used数组，使用引用形式。
- vector< int>& nums传入的集合。
- 确定递归函数终止条件：在记录 七十五【78.子集】知道需要搜集树形结构的所有节点，所以startindex的for循环判断限制了终止条件。所以此处可以省略。
- 确定逻辑：
- for循环从startindex开始，到nums.size()结束；
- 去重逻辑：if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)，所以nums要先排序。
- 把nums[i]放入temp。used标记更新。
- 递到下一层startindex = i+1.
- 回溯：从temp.pop_back()；在used标记更新。
代码实现
class Solution {
public:vector<vector<int>> result;vector<int> temp;void backtracking(int startindex,vector<bool>& used,vector<int>& nums){//每一步都要搜集结果result.push_back(temp);for(int i=startindex;i < nums.size();i++){//去重的逻辑if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}temp.push_back(nums[i]);used[i] = true;//递到下一层backtracking(i+1,used,nums);//回溯temp.pop_back();used[i] = false;}return;}vector<vector<int>> subsetsWithDup(vector<int>& nums) {result.clear();temp.clear();vector<bool> used(nums.size(),false);sort(nums.begin(),nums.end());backtracking(0,used,nums);return result;}
};
三、参考学习
90.子集II 参考学习链接
学习内容
- 知识点已经学过。那么分析一下时间复杂度。时间复杂度=递归次数 * 每次递归的时间复杂度。每次递归都是一个for循环，for循环最坏情况遍历整个nums。所以每次递归的时间复杂度是O(n)；递归次数：集合大小是n，子集总数是2n，所以递归次数是2n。时间复杂度是：O(n * 2n).
- 空间复杂度：每次递归没有开辟新的空间，使用的是temp，所以O(n)。
- 使用set去重版本。每一次递归新建一个unordered_set，如果是同一层，那么unordered_set中存在的元素，需要跳过。所以做到了同一层“树层”去重。
- 不用used数组也可以，因为组合startindex是从i+1，从该元素的后面选，不重复选取startindex之前的元素。
总结
90.子集II 综合了记录 六十七【40.组合总和II】的去重逻辑和记录 七十五【78.子集】每一个节点都搜集两个知识点。
（欢迎指正，转载标明出处）