public class Solution
{
    public IList<string> RemoveInvalidParentheses(string s)
    {
        var results = new HashSet<string>();
        Enumerate("", s, 0, results);
        return results.ToList();
    }

    private void Enumerate(string prefix, string s, int from, ISet<string> results)
    {
        if (from >= s.Length)
        {
            results.Add(prefix);
            return;
        }

        int balance = 0;
        for (int i = from; i < s.Length; i++)
        {
            if (s[i] == '(') balance++;
            else if (s[i] == ')') balance--;

            if (balance < 0)
            {
                for (int j = from; j <= i; j++)
                {
                    if (s[j] == '(' || s[j] == ')')
                    {
                        string newPrefix = s.Substring(from, i - from + 1);
                        newPrefix = newPrefix.Remove(j - from, 1);
                        Enumerate(prefix + newPrefix, s, i + 1, results);
                    }
                }
                return;
            }
        }

        if (balance == 0)
        {
            results.Add(prefix + s.Substring(from, s.Length - from + 1));
        }
    }
}