# Find biggest K, such that any subset of size less than K is not affecting the array

Let's say we have given array $A = \{a_1, a_2, a_3,\dots,a_n\}$ of size $n$, and integer $L$, we want to find biggest integer $K$, such that the array without any subset of size $x, x\leq K$ will have sum greater or equal to $L$.

Example

$A = \{1, 2,3\}, L = 2$, in this case $K = 1$, because any subset of size $1$ will not affect the array, or the array sum will be greater or equal to $L$. Note that $K$ cannot be $2$ because the array without the subset $\{2, 3\}$ has sum $1$ which is less than $L$.

What I think for the solution

I started thinking about solution with dynamic programming, I'm thinking in the following way, if we have $K$ for first $x$ elements and for sum $y$, we could come with relation to solve for $x+1$ elements and for $y+1$ for value of $L$, but I cannot come with the relation.

Runtime $O(N\cdot logN)$ or better for the sorting, $O(N)$ for computing the sum of the array, at most $O(N)$ iterations.