# Finding subset of integer summing up above threshold

Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such solution exists.

Clearly, a trivial solution is to take the maximal element $a_{max} = \max_{i} A_i$, multiply it by $m$, and if $ma_{max} \geq k$ return it.

Is there a polynomial time algorithm $X$ such that: $X$ is a randomized algorithm, and at every run, it outputs such $m$ elements where every $m$ elements have a positive probability to be generated by $X$? (for example, the above method does not satisfy it because on a given $A,m,k$ it will output one answer with probability 1, and many possible other solutions with probability 0). Is there an algorithm where every $m$ elements have an equal probability to be generated (i.e. the algorithm is uniform)?

• Pick a random subset of size $m$, if the sum is $\ge k$ return it, else return $(a_{max}, a_{max}, \dots)$. This algorithm has a positive probability of every solution being returned. – Jakube Sep 20 '18 at 10:12
• thanks! it will work. I edited and added uniform requirements, any ideas now? – SomeoneHAHA Sep 20 '18 at 11:05
• Since SUBSET-SUM is NP-hard, I would expect the answer to be 'no'. – Yuval Filmus Sep 20 '18 at 16:56
• Do you need an exactly uniform distribution on the set of all solutions; or only something that is approximately uniform? – D.W. Sep 20 '18 at 20:09
• Both are ok, but in the case of approximation, does it mean that there is no exact solution? – SomeoneHAHA Sep 20 '18 at 20:50