Solution 1

其实本题就是对 78. Subsets 的拓展，在DFS过程中增加一个额外的跳出判定，保证不会出现重复的子集。

这个思路实际上就是3sum里面枚举的思路，也就是先对整个输入序列排序，相同的元素必然会相邻，接着就是对相邻相同元素的判定处理了。

一开始，我以为只要判定相邻相同就跳出好了，但是发现输入序列1，2，2会因此跳过对子集1，2，2的搜索。

因此判定要稍稍复杂一点：增加一个搜索状态数组，按顺序枚举，如果出现当前元素与前一个元素相同而前一个元素未被使用的情形，那么需要跳出后续的搜索。因为按顺序搜索，如果前一个相同元素没被使用，此时必然已经完成了使用该元素的搜索过程，所以后续相同元素的搜索必然重复。

这里就不实现位运算了，因为本身逻辑是相同的，只是位表示更加简介清晰。

• 时间复杂度： O ( N × 2 N ) O(N \times 2^N) O(N×2N)，其中 N N N为输入序列的长度，这里没什么分析的了
• 空间复杂度： O ( N ) O(N) O(N)，其中 N N N为输入序列的长度，这里也没有什么可分析的了

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> current;
        int numLen = nums.size();
        
        sort(nums.begin(), nums.end());
        vector<bool> used(numLen, false);
        for (int i = 0; i <= numLen; i++) {
            this->dfs(ans, nums, current, 0, i, used);
        }
        
        return ans;
    }
private:
    void dfs(vector<vector<int>> & ans, vector<int> & nums, vector<int> & current, int pos, int numLen, vector<bool> & used) {
        if (current.size() == numLen) {
            // this->print("OUTPUT", current);
            ans.push_back(current);
            return;
        }
        for (int i = pos; i < nums.size(); ++i) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            current.push_back(nums[i]);
            used[i] = true;
            this->dfs(ans, nums, current, i + 1, numLen, used);
            used[i] = false;
            current.pop_back();
        }
    }
    
    void print(string input, vector<int> & test) {
        cout << input << " ";
        for (auto item: test) {
            cout << item << " ";
        }
        cout << endl;
    }
    
    void print(string input, vector<bool> & test) {
        cout << input << " ";
        for (auto item: test) {
            cout << item << " ";
        }
        cout << endl;
    }
};

Solution 2

Solution 1的Python实现

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans, current= list(), list()
        
        nums = sorted(nums)
        used = [False] * len(nums)
        for i in range(len(nums) + 1):
            self._dfs(ans, nums, current, 0, i, used)
        
        return ans
        
    def _dfs(self, ans: List[List[int]], nums: List[int], current: List[int], pos: int, numLen: int, used: List[bool]) -> None:
        if len(current) == numLen:
            ans.append(copy.deepcopy(current))
            return
        
        for i in range(pos, len(nums)):
            if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False:
                continue
                
            current.append(nums[i])
            used[i] = True
            self._dfs(ans, nums, current, i + 1, numLen, used)
            used[i] = False
            current.pop()