Why this fails: The time complexity of generating all subsequences is $O(2^N)$. For a string of length 25, this involves millions of operations. Additionally, checking validity takes $O(N)$ for each subsequence. This approach will result in a Time Limit Exceeded (TLE) error because it blindly explores invalid branches and does not utilize the information about which parentheses are causing the issue.

Core Insight for Remove Invalid Parentheses

The key to optimizing the solution lies in identifying the "target" state before starting the recursion. Instead of blindly removing characters, we first scan the string to determine exactly how many open parentheses ( and closed parentheses ) are misplaced.

1. Pre-calculation: Iterate through the string.
   • If we see (, increment a counter for expected closing parentheses.
   • If we see ), decrement the counter. If the counter is already 0, this ) is invalid and must be removed.
   • Any positive value remaining in the counter represents excess ( that must be removed.
2. State Management: We now have two specific constraints: rem_open (count of ( to remove) and rem_close (count of ) to remove).
3. Invariant: During our recursive traversal, we maintain a balance variable. balance increments on ( and decrements on ). If balance ever becomes negative, the current path is invalid (we closed more than we opened).

Visual Description: Imagine the recursion tree starting at the first index of the string. At each node (character), the tree branches. One branch represents "Keeping" the character (appending it to our potential solution). The other branch represents "Removing" the character (skipping it).

• The "Remove" branch is only taken if we still have a quota of removable characters (rem_open or rem_close > 0).
• The "Keep" branch is only taken if keeping the character maintains a non-negative balance.
• Duplicate branches (removing consecutive identical characters) are pruned to prevent duplicate results.

Execution Flow

Let's trace the logic for input s = "()())()".

1. Pre-calculation:
   • Scan finds one extra ).
   • left_rem = 0, right_rem = 1.
2. Start DFS at index 0.
3. Index 0 to 3 (()()): The algorithm keeps these as they are valid. balance fluctuates but stays $\ge 0$.
4. Index 4 ()):
   • We encounter the second ) in the sequence ...)).
   • Option A (Remove): Since right_rem > 0, we can skip this character. right_rem becomes 0. We proceed to build the rest. Result: (())().
   • Option B (Keep): We keep it. Balance updates. If balance goes negative, this branch dies.
5. Index 5 ((): Processed normally.
6. Index 6 ()): Processed normally.
7. Completion: When recursion hits the end, we verify left_rem, right_rem, and balance are all 0. Valid strings are added to a Set to handle uniqueness automatically.

Proof of Correctness

The algorithm is correct because it exhaustively explores all combinations of removals that match the minimum count calculated in the first step.

1. Minimality: By strictly enforcing left_rem and right_rem limits, we never remove more parentheses than absolutely necessary.
2. Validity: The balance >= 0 check during the "Keep" phase ensures that we never close a parenthesis that hasn't been opened. The final balance == 0 check ensures all opened parentheses are closed.
3. Completeness: The backtracking nature ensures we try removing every possible combination of the "bad" parentheses, ensuring we find all valid permutations.

Reference Implementation

C++ Solution for LeetCode 301

cpp
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int left_rem = 0, right_rem = 0;
        
        // Phase 1: Calculate minimum removals needed
        for (char c : s) {
            if (c == '(') {
                left_rem++;
            } else if (c == ')') {
                if (left_rem > 0) {
                    left_rem--;
                } else {
                    right_rem++;
                }
            }
        }
        
        unordered_set<string> result;
        string current_expr = "";
        
        // Phase 2: Backtracking
        backtrack(s, 0, left_rem, right_rem, 0, current_expr, result);
        
        return vector<string>(result.begin(), result.end());
    }

private:
    void backtrack(const string& s, int index, int l_rem, int r_rem, int balance, string& current, unordered_set<string>& result) {
        // Base Case: End of string
        if (index == s.length()) {
            if (l_rem == 0 && r_rem == 0 && balance == 0) {
                result.insert(current);
            }
            return;
        }
        
        char c = s[index];
        
        // Pruning: If balance is negative, this path is invalid (cannot recover)
        if (balance < 0) return;

        // Choice 1: Remove current character (only if it's a paren and we have quota)
        if (c == '(' && l_rem > 0) {
            backtrack(s, index + 1, l_rem - 1, r_rem, balance, current, result);
        } else if (c == ')' && r_rem > 0) {
            backtrack(s, index + 1, l_rem, r_rem - 1, balance, current, result);
        }
        
        // Choice 2: Keep current character
        current.push_back(c);
        
        if (c != '(' && c != ')') {
            // It's a letter, balance doesn't change
            backtrack(s, index + 1, l_rem, r_rem, balance, current, result);
        } else if (c == '(') {
            backtrack(s, index + 1, l_rem, r_rem, balance + 1, current, result);
        } else if (c == ')') {
            backtrack(s, index + 1, l_rem, r_rem, balance - 1, current, result);
        }
        
        // Backtrack
        current.pop_back();
    }
};

Java Solution for LeetCode 301

java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int leftRem = 0;
        int rightRem = 0;

        // Calculate misplaced parentheses
        for (char c : s.toCharArray()) {
            if (c == '(') {
                leftRem++;
            } else if (c == ')') {
                if (leftRem > 0) {
                    leftRem--;
                } else {
                    rightRem++;
                }
            }
        }

        Set<String> result = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        
        backtrack(s, 0, leftRem, rightRem, 0, sb, result);
        
        return new ArrayList<>(result);
    }

    private void backtrack(String s, int index, int lRem, int rRem, int balance, StringBuilder current, Set<String> result) {
        if (index == s.length()) {
            if (lRem == 0 && rRem == 0 && balance == 0) {
                result.add(current.toString());
            }
            return;
        }

        char c = s.charAt(index);
        
        // Optimization: Stop if balance goes negative (impossible to recover)
        if (balance < 0) return;

        // Logic to remove character
        // We only remove if we have a quota (lRem or rRem > 0)
        // To avoid duplicates, we could add logic here, or just rely on the Set
        if (c == '(' && lRem > 0) {
            backtrack(s, index + 1, lRem - 1, rRem, balance, current, result);
        } else if (c == ')' && rRem > 0) {
            backtrack(s, index + 1, lRem, rRem - 1, balance, current, result);
        }

        // Logic to keep character
        current.append(c);
        if (c != '(' && c != ')') {
            backtrack(s, index + 1, lRem, rRem, balance, current, result);
        } else if (c == '(') {
            backtrack(s, index + 1, lRem, rRem, balance + 1, current, result);
        } else if (c == ')') {
            backtrack(s, index + 1, lRem, rRem, balance - 1, current, result);
        }
        
        // Undo change (Backtrack)
        current.deleteCharAt(current.length() - 1);
    }
}

Python Solution for LeetCode 301

python
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        # Phase 1: Count invalid parentheses
        left_rem, right_rem = 0, 0
        for char in s:
            if char == '(':
                left_rem += 1
            elif char == ')':
                if left_rem > 0:
                    left_rem -= 1
                else:
                    right_rem += 1
        
        result = set()
        
        # Phase 2: DFS Backtracking
        def backtrack(index, l_rem, r_rem, balance, current_path):
            # Base Case: End of string
            if index == len(s):
                if l_rem == 0 and r_rem == 0 and balance == 0:
                    result.add("".join(current_path))
                return

            # Pruning: Balance cannot be negative
            if balance < 0:
                return

            char = s[index]

            # Decision 1: Remove the character
            # Only possible if we have removals left for that type
            if char == '(' and l_rem > 0:
                backtrack(index + 1, l_rem - 1, r_rem, balance, current_path)
            elif char == ')' and r_rem > 0:
                backtrack(index + 1, l_rem, r_rem - 1, balance, current_path)

            # Decision 2: Keep the character
            current_path.append(char)
            
            if char == '(':
                backtrack(index + 1, l_rem, r_rem, balance + 1, current_path)
            elif char == ')':
                backtrack(index + 1, l_rem, r_rem, balance - 1, current_path)
            else:
                # Letters don't affect balance
                backtrack(index + 1, l_rem, r_rem, balance, current_path)
            
            # Backtrack step
            current_path.pop()

        backtrack(0, left_rem, right_rem, 0, [])
        return list(result)