The number of characters you have to delete is not something the search discovers, it is known before the search starts. One left-to-right pass counts the `)` that arrive with nothing open and the `(` left dangling at the end; those two numbers, `rmL` and `rmR`, are the exact budget, and every valid answer spends it in full. That turns an open-ended “try removing things” into a fixed-depth walk over the string with two quotas in hand. The approach I passed on is the BFS the problem seems to be asking for: take the original string, generate every string with one character removed, test each for validity, and if none pass, expand the next level. It is correct, and it earns the word “minimum” honestly, because the first level that yields anything valid is minimal by construction. The cost is that level `k` materializes up to `C(25, k)` fresh string copies, and the only thing keeping that from exploding twice over is a hash set catching duplicates, which are the majority of what gets generated. Computing the budget up front keeps the same minimality guarantee without ever building a string you then throw away. What remains is one decision per character: for a bracket, recurse once without it and pay a quota, once with it and move `open`; for a letter there is nothing to decide. Three guards keep the tree honest — a quota going negative, `open` going negative, and the tail being shorter than the quota still owed. ## Worked example `s = "(a)())()"`. The counting pass, with `open` for unspent `(` and `rmR` for every `)` that arrives too early: - `i=0 '('` → `open` 1 - `i=1 'a'` → not a bracket, ignored - `i=2 ')'` → spends the open bracket, `open` 0 - `i=3 '('` → `open` 1 - `i=4 ')'` → `open` 0 - `i=5 ')'` → nothing open, this one can never be matched → `rmR` 1 - `i=6 '('` → `open` 1 - `i=7 ')'` → `open` 0 So `rmL = 0` and `rmR = 1`: delete exactly one `)` and keep every `(`. Three positions survive the walk — dropping index 2 gives `(a())()`, dropping index 4 gives `(a)()()`, and dropping index 5 gives `(a)()()` again, because those two closers sit next to each other and are interchangeable. The set folds the pair into one, and the answer is the two distinct strings. ## Complexity - Time O(n · 2^p), `p` being the number of brackets — each bracket forks twice and every surviving path pays one string insert; the quota guards cut most of that tree, not its worst case. - Space O(n) — recursion depth plus the single `cur` buffer that is pushed and popped, on top of the output set. ## Code (C++) ```cpp class Solution { public: vector removeInvalidParentheses(string s) { int rmL = 0, rmR = 0; for (char c : s) { if (c == '(') { ++rmL; } else if (c == ')') { if (rmL > 0) --rmL; else ++rmR; } } set seen; string cur; dfs(s, 0, 0, rmL, rmR, cur, seen); return vector(seen.begin(), seen.end()); } private: void dfs(const string& s, int i, int open, int rmL, int rmR, string& cur, set& seen) { if (rmL < 0 || rmR < 0 || open < 0) return; // nothing left to delete from: the remaining tail is shorter than the quota if ((int)s.size() - i < rmL + rmR) return; if (i == (int)s.size()) { if (open == 0 && rmL == 0 && rmR == 0) seen.insert(cur); return; } char c = s[i]; if (c == '(') { dfs(s, i + 1, open, rmL - 1, rmR, cur, seen); cur.push_back(c); dfs(s, i + 1, open + 1, rmL, rmR, cur, seen); cur.pop_back(); } else if (c == ')') { dfs(s, i + 1, open, rmL, rmR - 1, cur, seen); cur.push_back(c); dfs(s, i + 1, open - 1, rmL, rmR, cur, seen); cur.pop_back(); } else { cur.push_back(c); dfs(s, i + 1, open, rmL, rmR, cur, seen); cur.pop_back(); } } }; ``` ## One note The trap is assuming distinct deletion positions give distinct strings. In `(a)())()` the two adjacent `)` are indistinguishable, so a DFS that reports every successful path reports `(a)()()` twice, while the problem wants unique answers. `set` is the blunt fix and it hands you sorted output for free; the sharper one is to skip a run of identical brackets when choosing which to drop, which keeps the result a plain `vector` and costs a while loop. The other line worth keeping is the length guard, `s.size() - i < rmL + rmR`. Without it, an input of 25 consecutive `(` took 351 ms on this machine: every branch that keeps a bracket still walks to the end of the string before finding out there is no room left to meet the quota. With the guard, the same input returns immediately, because the first kept bracket leaves the tail one character too short and the whole subtree dies at depth 1. Transferable: when a problem says “minimum removals”, check whether the count is computable in one pass. If it is, the search stops being a search over depths and becomes a fixed-budget enumeration — no outer level loop, no “did this level produce anything” bookkeeping. And `open < 0` deserves its own guard instead of a validity check at the end: rejecting an impossible prefix at the character that breaks it is what stops the tree from growing a branch you will throw away.