Q: given a string of N left+right brackets, you can find out how many invalid chars to remove to make it balanced. Say it’s R. There are up to N-choose-R ways to make it balanced. Print all unique balanced strings in compact form.
subproblem: minimum how many invalid chars to remove
Useful preprocessing technique — on the left end, any closers must be removed. Same on the right end. No choice 🙂 We would end up with a valid char on each end. This is nice but optional in my Idea3 below.
— my idea 3 to count minimum cuts
Aha — There will surely be some “kernels” i.e. opener-then-closer in a row. First scan I will remove them, then remove more kernels. This is always optimal if we aim to minimize the cuts
-  ] [  ] [  ] becomes ]
- ][ becomes ][
-  [     becomes [
- [[][] becomes [
- []][]][ becomes ]][
What remain are the positions of bad chars. I need to remember these positions.
Case: closers only. Let’s look at one position like #55. We can cut #55 or another closer at an earlier position.
Case: openers only. Similar to the above.
Case: closers-openers. The original string is partitioned into exactly two sections, each similar to the above cases.