import java.util.*;

class Solution_BFS {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null) {
            return result;
        }

        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        // Initial state
        queue.offer(s);
        visited.add(s);

        boolean found = false; // Flag to indicate if we found the first valid string(s)

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // Process level by level

            for (int i = 0; i < levelSize; i++) {
                String current = queue.poll();

                // Check if the current string is valid
                if (isValid(current)) {
                    result.add(current);
                    found = true; // Mark that we've found solutions at this level
                }

                // If we already found solutions at this level,
                // no need to generate shorter strings (more removals)
                if (found) {
                    continue;
                }

                // Generate neighbors (remove one parenthesis)
                for (int j = 0; j < current.length(); j++) {
                    char ch = current.charAt(j);

                    // Only consider removing parentheses
                    if (ch == '(' || ch == ')') {
                        // Create the next string by removing the character at index j
                        String nextStr = current.substring(0, j) + current.substring(j + 1);

                        // If this neighbor hasn't been visited, add it to the queue and visited set
                        if (visited.add(nextStr)) { // Set.add() returns true if the element was not already present
                            queue.offer(nextStr);
                        }
                    }
                }
            }

            // If we found valid strings in this level, stop exploring further (deeper levels)
            if (found) {
                break;
            }
        }

        return result;
    }

    // Helper function to check if a string has valid parentheses
    private boolean isValid(String str) {
        int balance = 0;
        for (char ch : str.toCharArray()) {
            if (ch == '(') {
                balance++;
            } else if (ch == ')') {
                balance--;
            }
            // If balance drops below zero at any point, it's invalid
            if (balance < 0) {
                return false;
            }
        }
        // For a valid string, the final balance must be zero
        return balance == 0;
    }
}

import java.util.*;

class Solution_DFS {
    private Set<String> resultSet = new HashSet<>();
    private String originalString;
    private int len;
    private int minLeftToRemove;
    private int minRightToRemove;

    public List<String> removeInvalidParentheses(String s) {
        this.originalString = s;
        this.len = s.length();
        this.resultSet.clear(); // Clear for potential multiple calls

        // Step 1: Calculate minimum removals needed
        int left = 0, right = 0;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                left++;
            } else if (ch == ')') {
                if (left > 0) {
                    left--; // Matched a '('
                } else {
                    right++; // Unmatched ')' found, needs removal
                }
            }
        }
        this.minLeftToRemove = left;  // Remaining unmatched '(' need removal
        this.minRightToRemove = right; // Already counted unmatched ')'

        // Step 2: Start DFS
        dfs(0, 0, 0, minLeftToRemove, minRightToRemove, new StringBuilder());

        return new ArrayList<>(resultSet);
    }

    /**
     * DFS function to explore possibilities.
     *
     * @param index Current index in the original string.
     * @param leftCount Count of '(' included in currentPath so far.
     * @param rightCount Count of ')' included in currentPath so far.
     * @param leftRem Remaining '(' to remove.
     * @param rightRem Remaining ')' to remove.
     * @param currentPath StringBuilder building the potential result.
     */
    private void dfs(int index, int leftCount, int rightCount, int leftRem, int rightRem, StringBuilder currentPath) {
        // Base case: Reached the end of the original string
        if (index == len) {
            // If we removed the exact required number of parentheses and the result is valid
            if (leftRem == 0 && rightRem == 0 && leftCount == rightCount) { // leftCount == rightCount implicitly checks validity here
                resultSet.add(currentPath.toString());
            }
            return;
        }

        // Pruning: If we have already removed too many, stop this path
        if (leftRem < 0 || rightRem < 0) {
            return;
        }
         // Pruning: If rightCount exceeds leftCount, this path cannot lead to a valid solution
        if (rightCount > leftCount) {
             return;
        }


        char currentChar = originalString.charAt(index);
        int pathLength = currentPath.length(); // Store length for backtracking

        if (currentChar == '(') {
            // Option 1: Remove '('
            dfs(index + 1, leftCount, rightCount, leftRem - 1, rightRem, currentPath);

            // Option 2: Keep '('
            currentPath.append('(');
            dfs(index + 1, leftCount + 1, rightCount, leftRem, rightRem, currentPath);
            currentPath.setLength(pathLength); // Backtrack

        } else if (currentChar == ')') {
            // Option 1: Remove ')'
            dfs(index + 1, leftCount, rightCount, leftRem, rightRem - 1, currentPath);

            // Option 2: Keep ')' - only if it maintains validity (rightCount < leftCount)
            // This check is implicitly handled by the pruning `rightCount > leftCount` above,
            // but explicitly checking here can also work: if (leftCount > rightCount) { ... }
            // We rely on the pruning check at the start of the function.
            currentPath.append(')');
            dfs(index + 1, leftCount, rightCount + 1, leftRem, rightRem, currentPath);
            currentPath.setLength(pathLength); // Backtrack

        } else {
            // If it's a letter, just keep it
            currentPath.append(currentChar);
            dfs(index + 1, leftCount, rightCount, leftRem, rightRem, currentPath);
            currentPath.setLength(pathLength); // Backtrack
        }
    }
}

// 以处理 '(' 为例：
currentPath.append('(');      // 选择保留该括号
dfs(...);                     // 继续探索
currentPath.setLength(pathLength); // 回溯：撤销选择

// 示例 1：
输入: "()())()"
输出: ["()()()", "(())()"]

// DFS处理流程：
1. 预计算需删除 1 ')'
2. 递归树中优先尝试删除第3个')'和第5个')'
3. 通过回溯保留有效组合

// BFS 方案：
使用 HashSet 存储已访问字符串

// DFS 方案：
自然避免重复，因为：
1. 总是按顺序处理字符
2. 删除选择具有确定性
3. 结果存储在Set中自动去重

// 在DFS中加入记忆缓存
private Map<String, Boolean> memo = new HashMap<>();

// 修改递归入口：
if (memo.containsKey(currentPath.toString())) {
    return;
}
memo.put(currentPath.toString(), true);

// 在DFS开始时加入长度判断
int maxPossibleLength = len - (minLeftToRemove + minRightToRemove);
if (currentPath.length() + (len - index) < maxPossibleLength) {
    return;
}