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)()()

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);
            }
        }
    }
}