Given a collection $S$ with up to $1,000,000$ values where $0 < S_i < 100$. I need to find the top $k$ groups whose sum is bigger than $N$ where $0 < k < 1,000$ and $N$ is a big positive number. The groups are sub-collections of $S$ where duplicates are allowed.
Ex: for $S=[1.1,3], k = 2, N=4$ the solution is:
- $[1.1, 3] \rightarrow 4.1$
- $[1.1, 1.1, 1.1, 1.1] \rightarrow 4.4$
I am not sure how to approach this, I been trying to sort $S$ from small to big, then start with a group made of $S_1$, then replace one of the variables with $s_2$ and remove as many $S_1$ as I can, repeat the process until I got no $S_1$ in the group and continue with $S_2$. But this don't cover all the cases. And it's a very slow method.
Found a probabilistic solution that cover all the cases.
Pick values in random from $S$ until the sum is above $N$. Repeat the process multiple times while kipping the top $k$ best results.
I hope others will be able to find a better solution.