2021.3.30

90. 子集II

https://leetcode-cn.com/problems/subsets-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

学到的知识点：位掩码（学歪来
位掩码，haowan
这个方法是在 1178.猜字谜 中学到的，使用一个int型数的每一二进制位代表集合中的一项。
使用以下代码可以很方便地循环求出这个位掩码所代表的集合的全部不重复子集：

//int mask=原集合状态压缩后的数
//int subset=mask
do{
  subset = (subset - 1) & mask;//其中每一次循环得到的subset就是mask的全部子集，不会重复
}while(subset!=mask);
//由于int型数据在存储时使用的是二进制补码，所以当subset==0时，subset-1的结果为二进制的全1
//再与mask做&运算即可得到subset==mask，退出循环。

最终代码（C++）：

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ansList;
        //由于要求原集合的子集，所以每一个数都需要用到，故代表原集合的位掩码为全1
        int bitMask = (int)pow(2, nums.size()) - 1;
        int subset = bitMask;
        do
        {
            vector<int> tempList;
            subset = (subset - 1) & bitMask;//其中每一次循环得到的subset就是mask的全部子集，不会重复
            for (int i = 0; i < nums.size(); i++)
            {
                if (((subset >> i) & 1) == 1)
                {
                    tempList.push_back(nums[i]);
                }
            }//得到一个子集存储于tempList中
            //判断ansList中是否存在与tempList相等的vector，不存在则加入。
            sort(tempList.begin(), tempList.end());
            vector<vector<int>>::iterator ret = find(ansList.begin(), ansList.end(), tempList);
            if (ret == ansList.end())
            {
                ansList.push_back(tempList);
            }
        } while (subset != bitMask);
        return ansList;
    }
};