Количество уникальных подмножеств из набора с повторяющимися элементами

Дан массив arr[] размера N . Задача состоит в том, чтобы подсчитать количество уникальных подмножеств.

Примеры:

Input: arr[] = {1, 2, 2}
Output: 6
Explanation: Total possible subsets of this set  = 2³= 8. 
Following are the all 8 subsets formed from arr[].
{}, {1}, {2}, {2}, {1, 2}, {1, 2}, {2, 2}, {1, 2, 2}. 
These are all possible subsets out of which {2} and {1, 2} are repeated.
Therefore there are only 6 unique subsets of given set.

Input: arr[] = {1, 3, 3, 4, 4, 4}
Output: 24

Наивный подход: в базовом подходе создайте все подмножества набора и сохраните их в std::set, который хранит только уникальные элементы. Но это не эффективный по времени подход.

Временная сложность: O(2 ^N )
Вспомогательное пространство: O(N * 2 ^N-1 )

Эффективный подход: можно заметить, что не требуется находить все подмножества. Единственная проблема состоит в том, чтобы найти количество уникальных подмножеств. Основываясь на том, сколько раз каждый элемент вносит свой вклад в уникальные подмножества, это можно сделать с помощью математических манипуляций и, наконец, получить формулу.

Следуйте приведенному ниже наблюдению, чтобы получить формулу.

For each unique value val_i say the frequency of that element is freq[val_i].
So each unique value has (freq[val_i] + 1) to be present in a unique subset
because it can be present 0 times, 1 time, 2 times . . . freq[val_i] times in a subset.
Now this is true for all such unique elements.
Therefore, The number of unique subsets of a set  = Product of (frequency+1) of each element.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: НА)