90 Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

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],
  []
]

The Idea: Implement the power set recursive formula, with the added benefit of ignoring duplicates. Duplicates can be used if we first sort the vector, and then append to an unordered_set. Sorting the vector essentially renders the ordering the vector obsolete, and the unordered_setavoids direct duplication.

The powerset begins with the empty set, and the build across each set by appending a character to end of each set.

case 1: {}                         = P(0) (empty set);      2^0 = 1
case 2: {}, {a}                    = P('a');                2^1 = 2
case n: {}, {a}, {b}, {ab}         = P('ab');               2^2 = 4

' '
' ' a 
' ' a b ab 
' ' a b ab c ac bc abc 
' ' a b ab c ac bc abc d ad bd abd cd acd bcd abcd

Complexity: O(n^2) time and space

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }
        return seed;
    }
};

vector<vector<int>> subsetsWithDup(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    unordered_set<vector<int>, VectorHash> unique_set;
    unique_set.reserve(1 << nums.size()); // pow(2, nums.size())
    unique_set.insert(vector<int>());

    for (int i = 1; i <= nums.size(); i++) {
        int cur_size = unique_set.size();

        unordered_set<vector<int>, VectorHash> unique_set_cp = unique_set;
        for (auto &v : unique_set_cp) {
            vector<int> next = v;
            next.push_back(nums.at(i - 1));
            unique_set.insert(next);
        }
    }

    vector<vector<int>> unique_subsets;
    unique_subsets.reserve(1 << nums.size());

    for (auto &v : unique_set)
        unique_subsets.push_back(v);

    return unique_subsets;
}

Testing

int main()
{
    //vector<int> t1 = { 1,2,2 };
    //print2d(subsetsWithDup(t1));

    //vector<int> t2 = { 1,2,3 };
    //print2d(subsetsWithDup(t2));

    vector<int> t3 = { 4, 4, 4, 1, 4 };
    print2d(subsetsWithDup(t3));
}