leetcode90 子集II

1. 题意

给一个可能含有重复元素的数组，求这个数组的所有子集。

2. 题解

跟leetcode 72 子集的差别在于，我们需要将重复的元素给去掉。那如何去重呢，实际上我们可以先排序将重复的元素给放在一起。然后在回溯后，找到下一个不与当前元素相同的位置。

2.1 枚举选哪个

class Solution {vector<vector<int>> ans;vector<int> tmp;void dfs(vector<int> &nums, int depth) {ans.push_back(tmp);int sz = nums.size();for (int i = depth;i <sz; i++) {tmp.push_back( nums[i] );dfs( nums, i + 1);tmp.pop_back();while (i + 1 < sz && nums[i + 1] == nums[i]) {i++;}}   }
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort( nums.begin(), nums.end() );dfs(nums, 0);return ans;}
};

2.2 选或不选

class Solution {
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {ranges::sort(nums);int n = nums.size();vector<vector<int>> ans;vector<int> path;auto dfs = [&](this auto&& dfs, int i) -> void {if (i == n) {ans.push_back(path);return;}// 选 xint x = nums[i];path.push_back(x);dfs(i + 1);path.pop_back(); // 恢复现场// 不选 x，跳过所有等于 x 的数// 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了i++;while (i < n && nums[i] == x) {i++;}dfs(i);};dfs(0);return ans;}
};

Ref

0x3f