@@ -0,0 +1,1662 @@
+package com.interview.recursion;%0A%0Aimport java.util.*;%0A%0A/**%0A * Created by tushar_v_roy on 2/23/16.%0A */%0Apublic class RemoveInvalidParenthesis %7B%0A%0A    public List%3CString%3E removeInvalidParentheses(String s) %7B%0A        Set%3CString%3E res = new HashSet%3C%3E();%0A        int rmL = 0, rmR = 0;%0A        for(int i = 0; i %3C s.length(); i++) %7B%0A            if(s.charAt(i) == '(') rmL++;%0A            if(s.charAt(i) == ')') %7B%0A                if(rmL != 0) rmL--;%0A                else rmR++;%0A            %7D%0A        %7D%0A        DFS(res, s, 0, rmL, rmR, 0, new StringBuilder());%0A        return new ArrayList%3CString%3E(res);%0A    %7D%0A%0A    public void DFS(Set%3CString%3E res, String s, int i, int rmL, int rmR, int open, StringBuilder sb) %7B%0A        if(i == s.length() && rmL == 0 && rmR == 0 && open == 0) %7B%0A            res.add(sb.toString());%0A            return;%0A        %7D%0A        if(i == s.length() %7C%7C rmL %3C 0 %7C%7C rmR %3C 0 %7C%7C open %3C 0) return;%0A%0A        char c = s.charAt(i);%0A        int len = sb.length();%0A%0A        if(c == '(') %7B%0A            DFS(res, s, i + 1, rmL - 1, rmR, open, sb);%0A            DFS(res, s, i + 1, rmL, rmR, open + 1, sb.append(c));%0A%0A        %7D else if(c == ')') %7B%0A            DFS(res, s, i + 1, rmL, rmR - 1, open, sb);%0A            DFS(res, s, i + 1, rmL, rmR, open - 1, sb.append(c));%0A%0A        %7D else %7B%0A            DFS(res, s, i + 1, rmL, rmR, open, sb.append(c));%0A        %7D%0A%0A        sb.setLength(len);%0A    %7D%0A%0A    public static void main(String args%5B%5D) %7B%0A%0A        String s = %22(r(()()(%22;%0A        RemoveInvalidParenthesis rmp = new RemoveInvalidParenthesis();%0A        List%3CString%3E result = rmp.removeInvalidParentheses(s);%0A        result.forEach(s1 -%3E System.out.println(s1));%0A    %7D%0A%7D%0A

Remove invalid parentheses to get all combinations of result