力扣日记：【回溯算法篇】90. 子集 II
日期：2023.1.31
参考：代码随想录、力扣
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
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> results;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
// 记得先排序！！！
sort(nums.begin(), nums.end());
backtracking(nums, 0);
return results;
}
void backtracking(vector<int>& nums, int startindex) {
// 不需要终止条件
results.push_back(path);
// for
for (int i = startindex; i < nums.size(); i++) {
// 去重
if (i > startindex && nums[i] == nums[i-1]) {
// 第一个元素不用去重
// 如果本次取出元素与上一个元素一样，则跳过该元素
continue;
}
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
};
复杂度
时间复杂度: O(n * 2^n)
空间复杂度: O(n)
思路总结
- 本题在 78.子集 的基础上，添加了重复元素，且要对解集进行去重。去重的思路与 40.组合总和 II 完全一致。直接用
if (i > startindex && nums[i] == nums[i-1])为条件跳过(continue)同一层for循环的重复元素即可（即所谓“树层去重”) - 记得去重前一定要对原集合进行排序！！！
