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

        private void Enumerate(string s, ISet<string> results)
        {
            int balance = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '(') balance++;
                else if (s[i] == ')') balance--;

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

            if (balance == 0)
            {
                results.Add(s);
            }
        }
    }