You are given a string S that contains parentheses and letters. You have to remove the minimum number of invalid parentheses to make the input string valid.
Return all the possible results in the sorted order.
Example 1:
Input: S = "()())()"
Output: ["(())()","()()()"]
Example 2:
Input: S = "(a)())()"
Output: ["(a())()","(a)()()"]
Example 3:
Input: S = ")("
Output: [""]
Your Task:
You don't need to read input or print anything. Your task is to complete the function removeInvalidParentheses() which takes the string S as an input parameter and returns an array of strings representing all the valid parentheses that we can form by removing the minimum number of characters from the string.

Expected Time Complexity: O(2^{|S|})
Expected Auxiliary Space: O(1)
Constraints:
1 <= |S| <= 20
S consists of lowercase English letters and parentheses '(' and ')'

见题面

见题面