My sulution a has n^2 * 2 ^ n and get TL
accepted solution supposed to be O(n * 2^n), right?

You can manage with a blunt force solution, but you have to make it at least slightly optimized. I got AC in 1.8s by recursively searching for available combos of 3, and if on another step there were none, i searched for positions to destroy at least one.

1000 1000 1000 50 50 1000 1000 1000 1 1 1 1000 1000 1000 50 50
in this case you need to shot combos of 2 (50 50) earlier then combos of 3 (1 1 1)  (when combos (1000 1000 1000) are shoted)