## Remove Invalid Parentheses

• Time:O(2^n)
• Space:O(n + |\texttt{ans}|)

## C++

``````class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> ans;
const auto [l, r] = getLeftAndRightCounts(s);
dfs(s, 0, l, r, ans);
return ans;
}

private:
// very similar to 921. Minimum Add to Make Parentheses Valid
// return how many '(' and ')' need to be deleted
pair<int, int> getLeftAndRightCounts(const string& s) {
int l = 0;
int r = 0;

for (const char c : s)
if (c == '(')
++l;
else if (c == ')') {
if (l == 0)
++r;
else
--l;
}

return {l, r};
}

void dfs(const string& s, int start, int l, int r, vector<string>& ans) {
if (l == 0 && r == 0 && isValid(s)) {
ans.push_back(s);
return;
}

for (int i = start; i < s.length(); ++i) {
if (i > start && s[i] == s[i - 1])
continue;
if (l > 0 && s[i] == '(')  // delete s[i]
dfs(s.substr(0, i) + s.substr(i + 1), i, l - 1, r, ans);
if (r > 0 && s[i] == ')')  // delete s[i]
dfs(s.substr(0, i) + s.substr(i + 1), i, l, r - 1, ans);
}
}

bool isValid(const string& s) {
int count = 0;  // # of '(' - # of ')'

for (const char c : s) {
if (c == '(')
++count;
else if (c == ')')
--count;
if (count < 0)
return false;
}

return true;  // count == 0
}
};
``````

## JAVA

``````class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
final int[] counts = getLeftAndRightCounts(s);
dfs(s, 0, counts[0], counts[1], ans);
return ans;
}

// very similar to 921. Minimum Add to Make Parentheses Valid
// return how many '(' and ')' need to be deleted
private int[] getLeftAndRightCounts(final String s) {
int l = 0;
int r = 0;

for (final char c : s.toCharArray())
if (c == '(')
++l;
else if (c == ')') {
if (l == 0)
++r;
else
--l;
}

return new int[] {l, r};
}

private void dfs(final String s, int start, int l, int r, List<String> ans) {
if (l == 0 && r == 0 && isValid(s)) {
return;
}

for (int i = start; i < s.length(); ++i) {
if (i > start && s.charAt(i) == s.charAt(i - 1))
continue;
if (l > 0 && s.charAt(i) == '(') // delete s[i]
dfs(s.substring(0, i) + s.substring(i + 1), i, l - 1, r, ans);
else if (r > 0 && s.charAt(i) == ')') // delete s[i]
dfs(s.substring(0, i) + s.substring(i + 1), i, l, r - 1, ans);
}
}

private boolean isValid(final String s) {
int count = 0; // # of '(' - # of ')'

for (final char c : s.toCharArray()) {
if (c == '(')
++count;
else if (c == ')')
--count;
if (count < 0)
return false;
}

return true; // count == 0
}
}
``````

## Python

``````class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def getLeftAndRightCounts(s: str) -> tuple:
l = 0
r = 0

for c in s:
if c == '(':
l += 1
elif c == ')':
if l == 0:
r += 1
else:
l -= 1

return l, r

def isValid(s: str):
count = 0  # number of '(' - # of ')'
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return True  # count == 0

ans = []

def dfs(s: str, start: int, l: int, r: int) -> None:
if l == 0 and r == 0 and isValid(s):
ans.append(s)
return

for i in range(start, len(s)):
if i > start and s[i] == s[i - 1]:
continue
if r > 0 and s[i] == ')':  # delete s[i]
dfs(s[:i] + s[i + 1:], i, l, r - 1)
elif l > 0 and s[i] == '(':  # delete s[i]
dfs(s[:i] + s[i + 1:], i, l - 1, r)

l, r = getLeftAndRightCounts(s)
dfs(s, 0, l, r)
return ans
``````