Unique Sub Arrays

Given a collection of integers nums that might contain duplicates, return all possible sub-arrays of nums.

Note: The solution set must not contain duplicate subsets.

Ex.1 nums = {1, 2, 2}

0: 2
1:
2: 1
3: 1  2  2
4: 1  2
5: 2  2

Ex.2  nums = {1, 2, 3}

0: 2
1:
2: 1  2  3
3: 1
4: 3
5: 1  2
6: 2  3

The Idea: Define a hash for an unordered_setof vectors. Then double loop through the collection for every possible subarray size.

Complexity: O(n^2) time and O(2*n^2) 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) {
    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++) {
        for (int j = 0; j <= nums.size() - i; j++) {
            unique_set.insert(vector<int>(nums.begin() + j, nums.begin() + j + i));
        }
    }

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

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

    return unique_subsets;
}

Last updated