count number of subsets with atmost k distinct elements

Question

given a set of inetegers, count the number of subsets with atmost k distinct elements.
eg: set is {1,1,2,3,3} and k = 2:

possible subsets are:
{} - empty set
{1}
{1}
{2}
{3}
{3}
{1,1}
{1,2}
{1,3}
{1,3}
{1,2}
{1,3}
{1,3}
{2,3}
{2,3}
{1,1,2}
{1,1,3}
{1,1,3}
{1,3,3}
{1,3,3}
{2,3,3}
{1,1,3,3}
my solution was to iterate all the possible subsets and check whether there are less k+1 elements.. but it was so slow.. O(2^n)

Answer 1

Let's compress your set of values to a representation like S = [1:2, 2:1, 3:2] where you just save the value and the count for every element and assign them some order. Let n be the size of the sequence S. You then have 2^count possibilities to select a subset for every value.

For every group you have to decide whether to take it or not. If you take it, the number of distinct values increases and you have 2^count - 1 possibilities to do so. If not, the number of distinct values stays the same.

This yields the following DP approach: Let f(i, k) be the number of ways to make decisions from index i on, given that you are only allowed to use k more distinct values.

The recurrence is

f(n, k) = 1   if k >= 0
f(n, k) = 0   if k < 0
f(i, k) = f(i + 1, k) + (2^count[i] - 1) * f(i + 1, k - 1)

Leading to an O(n * k) algorithm. The result will be f(0, k).