Here is the interview question prompt, presented for reference.

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all the possible results.


For example, consider the following string as input: s = "()())()" The correct solution should return ["(())()","()()()"], with both possibilities.

Note: this problem is similar to Minimum Parentheses Removal, with the difference being that we want to return all possible valid string results.

Constraints

• 1 <= s.length <= 25
• s consists of lowercase English letters and parentheses '(' and ')'.
• There will be at most 20 parentheses in s.

You can see the full challenge with visuals at this link.