【Leetcode】90. Subsets II（思维）（重复数据的子集）（划重点）

约定不等于承诺〃 2022-02-22 19:26 194阅读 0赞

Given a collection of integers that might contain duplicates, ***nums***, return all possible subsets (the power set).

**Note:** The solution set must not contain duplicate subsets.

**Example:**

Input: [1,2,2]
    Output:
    [
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]

题目大意：

找出输入数组的全部子集，所有子集中不含有重复子集。

解题思路：

重新排列子集之后，我们可以发现一些规律：\[\],\[1\],\[2\],\[1,2\],\[2,2\],\[1,2,2\]

将输入的列表进行sort，我们可以看出，从开始的\[\]

搜索到1，发现1为一个新的元素，复制\[\]，添加\[1\]

搜索到2，发现2为一个新的元素，复制\[\]、\[1\]，添加\[2\]、\[1,2\]

搜索到2，发现2为一个重复元素，**此时复制\[\]、\[1\]，添加\[2\]、\[1,2\]则为重复**，所以我们只需要对前面加入第一个2时的元素添加的\[2\]、\[1,2\]进行复制添加\[2,2\]、\[1,2,2\]

所以我们可以得出规律，如果是新元素则复制当前答案中所有组合，添加新元素。如果是重复的元素，只复制添加当前元素的生成的所有组合。

class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            int len = nums.size();
            sort(nums.begin(), nums.end());
            
            vector<vector<int>> ans={
       {}};
            
            for(int i = 0, n=0;i<len;i++){
                int j = !i || nums[i-1]!=nums[i] ? 0:n;
                n = ans.size();
                for(; j<n;j++){
                    ans.push_back(ans[j]);
                    ans.back().push_back(nums[i]);
                }
            }
            
            return ans;
            
        }
    };