String: Combinations Using Recursion

Problem: Given a string of N characters, write a program to produce all combination of the characters. String "abc" should produce "a", "b", "c", "ab" , "ac", "bc", "abc". Solution: The recursive solution proposed below runs in O(2 ^ n). Pseudo Code:
1. If input string length = 1 
      return a list with the input string in it
2. if input string length > 1
      a. Get list of combinations recursively for sub string  without the 
         1st character
      b. Prepend the 1st character to all the combinations received from step a. and
         add to a new list of combinations;
      c. Add all strings from step a. above
      d. Add the 1st character to the new list of combinations
      e. return this new list of combinations
Code (C#):
        static List GetCombinations(string inputStr, int index)
            List newCombinations = new List();
            if (index == inputStr.Length - 1)
                List combinations = GetCombinations(inputStr, index + 1);
                foreach (string str in combinations)
                    newCombinations.Add(inputStr[index].ToString() + str);
            return newCombinations;

1 comment:

  1. This is what I am looking for. Too good. Thanks.