### pas.andrei's blog

By pas.andrei, 7 years ago,

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.

• +4

 » 7 years ago, # |   +4 This might be helpful.
 » 7 years ago, # |   0 Could you kindly provide the link of the problem? :)
•  » » 7 years ago, # ^ |   0 I could have provided a link, but the statement is in romanian. Anyway I finally solved this problem.
 » 7 years ago, # |   0 In order to solve the problem we should first create a vector of integers, let's call it S and an boolean array found, in which found[x] means that for the value x there was already found a subset whisch sums to x.We take all elements of the array a one by one: a1, a2, ..., an 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 in a and that we have m values in S, we now check for each j, 1 <= j <= m, if the value S[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). #include #include #include #include using namespace std; ifstream fin("fisier.in"); ofstream fout("fisier.out"); int a[1000]; bool found[50001]; vector S; int main() { int n, k, i, j, m; fin >> n >> k; for (i = 0; i < n; ++i) fin >> a[i]; found[0] = true; for (i = 0; i < n; ++i) { if (a[i] <= k) { if (found[a[i]] == false) { S.push_back(a[i]); found[a[i]] = true; m = S.size() - 1; } else m = S.size(); for (j = 0; j < m; ++j) { if (a[i] + S[j] <= k && found[a[i] + S[j]] == false) { S.push_back(a[i] + S[j]); found[a[i] + S[j]] = true; } } } } fout << S.size() + 1; return 0; }