using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Text.RegularExpressions;

​

public class Program

{

      // work out the states of the combination

      public static bool GetNextState(bool[] states)

      {

         for (var i = 0; i < states.Length; i++)

            if ((states[i] = !states[i]) == true)

               return false;

         return true;

      }

​

      // Create the combination

      public static string Join(string[] split, string[] matches, bool[] states)

      {

         var sb = new StringBuilder();

         for (var i = 0; i < states.Length; i++)

            sb.Append(split[i] + (states[i]? matches[i]:""));

         sb.Append(split.Last());

         return sb.ToString();

      }

​

      // enumerate the results

      public static IEnumerable<string> Results(string input)

      {

         var matches = Regex.Matches(input, @"\(.+?\)").Select(x => x.Value.Trim('(', ')')).ToArray();

         var split = Regex.Split(input, @"\(.+?\)");

         var states = new bool[matches.Length];

​

         do {

            yield return Join(split, matches, states);

         } while (!GetNextState(states));

      }

​

      public static void  Main(string[] args)

      {

​

         string s = "a(b)cd(ef)";

​

         foreach (var result in Results(s))

            Console.WriteLine(result);

      }

}

​

​