### pas.andrei's blog

By pas.andrei, 5 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.  Comments (4)
 » 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: 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 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; bool found; vector S; int main() { int n, k, i, j, m; fin >> n >> k; for (i = 0; i < n; ++i) fin >> a[i]; found = 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; }