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)
            {
                newCombinations.Add(inputStr.Substring(index));
            }
            else
            {
                List combinations = GetCombinations(inputStr, index + 1);
                foreach (string str in combinations)
                {
                    newCombinations.Add(str);
                    newCombinations.Add(inputStr[index].ToString() + str);
                }
                newCombinations.Add(inputStr[index].ToString());
            }
            return newCombinations;
        }