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] == ')')
                        {
                            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));
            }
        }
    }