Reference: LeetCode
Difficulty: Hard

## 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:

## Analysis

### Backtracking

Main function:

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.

Backtracking function:

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.