Leetcode90Subsets II

90. Subsets II

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.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

题解：

输入一个有重复元素的数组，列出该数组的所有子集；
例如：
输入：nums = [1,2,2]
输出：result = [[], [1], [1,2],[1,2,2],[2],[2,2]]

分析：

大体的思路和 Leetcode78：https://www.jianshu.com/p/8c0e958375d5 类似；
我们只需要在把item加入到result之前，用set判断这个item是否重复即可；
注：[1,2,1] 和 [1,1,2] 虽然元素排列次序不同，但其值也是相同的；为避免出现这种问题，我们事先将要输入的nums进行排序，这样一来，得到的item就是有序的了，然后再set去重得到最终结果。

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int i = 0;
        sort(nums.begin(), nums.end());
        vector<int> item;
        vector<vector<int>> result;
        set<vector<int>> judge;
        result.push_back(item);
        add_item(i, nums, judge, item, result);
        return result;
    }
private:
    void add_item(int i, vector<int> &nums, set<vector<int>> &judge, vector<int> &item, vector<vector<int>> &result) {
        if (i >= nums.size()) {
            return;
        }
        item.push_back(nums[i]);
        if (judge.find(item) == judge.end()) {
            result.push_back(item);
            judge.insert(item);
        }
        add_item(i + 1, nums, judge, item, result);
        item.pop_back();
        add_item(i + 1, nums, judge, item, result);
    }
};

int main() {
    vector<vector<int>> result;
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(2);
    Solution s;
    result = s.subsetsWithDup(nums);
    for (int i = 0; i < result.size(); i++) {
        if (result[i].size() == 0) {
            printf("[]");
        }
        for (int j = 0; j < result[i].size(); j++) {
            printf("[%d]", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

结果：

[]
[1]
[1][2]
[1][2][2]
[2]
[2][2]

My Solution:

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        item = []
        result = [[]]
        nums.sort()
        self.add_item(0, nums, item, result)
        return result
    def add_item(self, i, nums, item, result):
        if i >= len(nums):
            return
        item.append(nums[i])
        if result.count(item) == 0:         
            item_data = item.copy()
            result.append(item_data)
        self.add_item(i + 1, nums, item, result)   
        item.pop()
        self.add_item(i + 1, nums, item, result)