Given an array (multiset) of N elements, find the maximum number of subsets such that the sum of elements in each of the subsets is different and smaller than k.

Example: N = 4 a = {1, 1, 3, 5}

Out of all the 2^4 possible subsets of array a, 11 of them (including empty subset) have distinct sums.

Restricions: 1 <= N <= 1000 1 <= a[i] <= 50000 1 <= k <= 50000 Time limit: 0.4s Memory limit 16 MB

It is tagged as Dynamic Programming problem on the site I took it but I couldn't find any recursive formula in 2 days, so I thought that you can help me.

EDIT: I finally came up with a solution, which I'd rather classify as BFS.

This might be helpful.

Could you kindly provide the link of the problem? :)

I could have provided a link, but the statement is in romanian. Anyway I finally solved this problem.

In order to solve the problem we should first create a vector of integers, let's call it

Sand an boolean arrayfound, in whichfound[x]means that for the valuexthere was already found a subset whisch sums tox.We take all elements of the array a one by one:

a_{1},a_{2}, ...,a_{n}and if one of those number was not found already we insert it in S and mark it as found. Now, let's say we ar at the i-th element inaand that we havemvalues in S, we now check for each j,1 <= j <= m, if the valueS[j] + a[i]is new, and if it is we mark it as found and insert it in S. In the end, the answer is the amount of values in S + 1 (1 is for the empty subset).