Can somebody explain the fastest solution..please

#1

Can somebody explain the fastest solution…please

#2

we are trying to find the minimum length subsequence whose sum is closest to but less than sum/2.

#3

We do a knapsack on sum/2, while finding number of steps to reach each value upto sum/2.

Lets say we can reach sum/2-3 but not not sum2-2,sum/2-1 or sum/2, and that takes k steps, then we know the answer is simply k. Because we can make those k elements negative, and better answer is not possible.

We try to reach sum/2, because if we can do that perfectly, then the minimal gap will be 0,just make all those values negative, if the largest reachable value <= sum/2 is r, then we can reach a gap of ((sum-r) - r) and that is the best possible answer, we also store how many steps that requires along the way.

#4

The fastest solution is in correct and fails for the input [20, 10, 4]

#5

Well, the algorithm is all correct
But at the end, in the for loop, ‘j’ should be decremented after each iteration