Reference: LeetCode

Difficulty: Hard

My Post: Java Solution with Detailed Comments (easy-understand, readable)

## Problem

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

**Note:** The input string may contain letters other than the parentheses `(`

and `)`

.

**Example:**

1 | Input: "()())()" |

**Follow up:** Pruning

## Analysis

### Backtracking

Main function:

1 | public List<String> removeInvalidParentheses(String s) { |

The `getDeleteCount`

function helps determine how many `(`

and `)`

we will delete.

**Note:**

**This function is very important.**`(`

should be calculated starting from the right side of the array, which is opposed to the way we did for`(`

.- If this function does not provide correct number of
`(`

we should delete, you have to handle a lot of corner and special cases.

1 | // Return how many "(" and ")" should we delete. |

Backtracking function:

1 | /** |

**Time:** $O(2^N)$ is the upper bound, but we have pruning.**Space:** $O(N)$ because of call stacks.