I tried a lot but wasn’t able to find a solution that would pass in the given constraints. I think the completely correct solution for the problem is exponential. No one has been able to solve it completely till now.

Please look into the problem @taran_1407

@tehlka Your Code is not passing on this testcase

6 19 11

3 2 1 1 1 1

Your Code Output : NO

Correct Output :

YES

4

1 3 1 1 2

Since all weights can either be on left side, right side or neither, O(3^N) solution is possible.

But we can use DP, specifically f(p, x, y) denotes when considering first p weights, can we achieve x weight on left and y on right side? f(p, x, y) = f(p-1, x, y) || f(p-1, x-A_p, y) || f(p-1, x, y-A_p)

The time complexity of this approach would be O(N*(W/2)^2), roughly 25*10^8 iterations which is too much to pass, but that’s the best I can think right away. Some constant optimizations would be possible too.

Can you please confirm this once?.

I am not coming up with the complexity less than O(NW^2). Anyway first step is to write even a brute solution then we can improve it’s complexity. Give it a try please.