> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/recursion-and-backtracking/remove-parenthesis.md).

# Remove Parenthesis

You are given a string with '('  ')' and random characters. The expression is not balanced, but can be balanced by removing characters. Print all the valid expressions that can be generated by removing least number of characters required to balance the expression.

**Input Format**

```
Expression (String)
```

**Constraints**

```
1 <= Length of String <= 9
```

**Output Format**

```
1. Print all valid balanced expressions generated, each in separate line
2. Print only unique ones.
3. Print in order of euler path generation. 
```

**Sample Input 0**

```
(v)())()
```

**Sample Output 0**

```
(v())()
(v)()()
```

```java
public class Solution {
    Set<String> set = new HashSet<>();

    public void allRemovals(String str) {
        // Find minimum numbers of removals
        int unbalanced = min(str);
        balance(str, 0, 0, 0, "", unbalanced);
    }

    public int min(String str) {
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c != '(' && c != ')')
                continue;
            if (st.size() != 0)
                if (st.peek() == '(' && c == ')')
                    st.pop();
                else
                    st.push(c);
            else
                st.push(c);
        }
        return st.size();
    }

    public void balance(String str, int i, int l, int r, String ans, int unbalanced) {
        if (i == str.length()) {
            // Number of opeing backets == Number of closing brackets
            // & Removed brackets = Minimum
            if (l == r && unbalanced == 0)
                if (!set.containsKey(ans)) {
                    set.add(ans);
                    System.out.println(ans);
                }
            return;
        }
        if (unbalanced < 0)
            return;
        char c = str.charAt(i);
        if (r > l)
            return;
        else if (r == l) {
            if (c != '(' && c != ')')
                balance(str, i + 1, l, r, ans + c, unbalanced);
            // Ignoring a closing bracket
            else if (c == ')')
                balance(str, i + 1, l, r, ans, unbalanced - 1);
            else {
                // Ignore opening bracket
                balance(str, i + 1, l, r, ans, unbalanced - 1);
                // Include opening bracket
                balance(str, i + 1, l + 1, r, ans + c, unbalanced);
            }
        } else {
            if (c != '(' && c != ')')
                balance(str, i + 1, l, r, ans + c, unbalanced);
            else if (c == ')') {
                balance(str, i + 1, l, r, ans, unbalanced - 1);
                balance(str, i + 1, l, r + 1, ans + c, unbalanced);
            } else {
                balance(str, i + 1, l, r, ans, unbalanced - 1);
                balance(str, i + 1, l + 1, r, ans + c, unbalanced);
            }
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/recursion-and-backtracking/remove-parenthesis.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.