无锡网站排名推广,福州建设高端网站,网站工程师平均工资,关键字搜索软件1. 题意
给一个可能含有重复元素的数组#xff0c;求这个数组的所有子集。
2. 题解
跟leetcode 72 子集的差别在于#xff0c;我们需要将重复的元素给去掉。那如何去重呢#xff0c;实际上我们可以先排序将重复的元素给放在一起。然后在回溯后#xff0c;找到下一个不与…1. 题意
给一个可能含有重复元素的数组求这个数组的所有子集。
2. 题解
跟leetcode 72 子集的差别在于我们需要将重复的元素给去掉。那如何去重呢实际上我们可以先排序将重复的元素给放在一起。然后在回溯后找到下一个不与当前元素相同的位置。
2.1 枚举选哪个
class Solution {vectorvectorint ans;vectorint tmp;void dfs(vectorint 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:vectorvectorint subsetsWithDup(vectorint nums) {sort( nums.begin(), nums.end() );dfs(nums, 0);return ans;}
};2.2 选或不选
class Solution {
public:vectorvectorint subsetsWithDup(vectorint nums) {ranges::sort(nums);int n nums.size();vectorvectorint ans;vectorint 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
