题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

  1. 输入：nums = [1,2,2]
  2. 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

  1. 输入：nums = [0]
  2. 输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

    解题方法

    递归回溯

    通过递归回溯进行枚举，在横向搜索时，保证下一个元素与上一个元素不同，避免重复。
    时间复杂度O(n2^n)，空间复杂度O(n)
    C++代码： ```cpp class Solution { private: vector> result; vector cur;

public: void backtracking(vector& nums, int start) { result.push_back(cur); if(start==nums.size()) return; for(int i=start; i> subsetsWithDup(vector& nums) { sort(nums.begin(), nums.end()); backtracking(nums, 0);

  1.     return result;
  2. }

};

<a name="srjd0"></a>
## 迭代枚举
通过 `n` 位二进制数表示当前位是否被选取。当前位被选取而上一位与当前位相等的数字没有被选取时，表面该种情况已经被考虑过，不计入结果。<br />时间复杂度`O(n2^n)`，空间复杂度`O(n)`<br />**C++代码：**
```cpp
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> cur;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int mask=0; mask<(1<<n); mask++) {
            bool flag = true;
            cur.clear();
            for(int i=0; i<n; i++) {
                if(mask&(1<<i)) {
                    if(i>0 && (mask>>(i-1)&1)==0 && nums[i]==nums[i-1]) {
                        flag = false;
                        break;
                    }
                    cur.push_back(nums[i]);
                }
            }
            if(flag)    result.push_back(cur);
        }

        return result;
    }
};