How many subsets have a given sum, if the subsets can only contain at most $m$ elements?

1.2k Views Asked by At

Let set $S = \left \{ 1,2,3,4,5,6,\ldots,10,11,12 \right \}$.

Find how many sets are possible with a given sum and and upto given $m$.


For Ex : Take Sum = 6 and $m$ = size = $4$

The possible sets are : $\left \{ 2,4 \right \}, \left \{ 1,3,2 \right \}, \left \{ 1,4,1 \right \}, \left \{ 1,1,1,3 \right \}, \ldots$

but $\left \{ 1,1,1,1,2 \right \}$ is not valid as $m = 4$ and this contains $5$ elements


How many sets are possible with $m = 5$ and sum = $8$ ?

Is there any generalized idea to calculate sets ?

1

There are 1 best solutions below

3
On

The problem is similar to Subset Sum Problem(http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/) except you have one extra constraint of m.

After finding the all the sets with sum N, we can apply constraint on the size of m.