Remove Invalid Parentheses

Remove exactly the minimum

First scan to count unmatched left parentheses and unmatched right parentheses that must be removed. DFS through the string with index, open balance, and remaining removals. Always keep letters; for parentheses, choose keep when valid and remove when that removal remains. Never allow balance below zero, and emit only when all input and removals are exhausted with balance zero. Skip removing an identical parenthesis immediately after an already removed one at the same level to avoid duplicates. The bounded search is exponential in the worst case, which is unavoidable when many valid outputs exist; stack/path space is O(n) excluding results. Test only letters, already valid input, all parentheses invalid, repeated runs, and multiple minimum answers. BFS by deletion is valid but can retain many duplicate states.