Implement a function that prints all possible combinations of the characters in a string I came across this interview question and it has been asked to print combinations of the characters in a string. For example: "abc" --> a, b, c, ab, ac, bc, abc. Also it has been mentioned that 'ab' and 'ba' are same. 

I want to know if there is any improvement I can make in terms of memory usage/performance.

public string[] Combination(string str)
{
    if (string.IsNullOrEmpty(str))
        throw new ArgumentException("Invalid input");

    if (str.Length == 1)
        return new string[] { str };

    // read the last character
    char c = str[str.Length - 1];

    // apart from the last character send remaining string for further processing
    string[] returnArray = Combination(str.Substring(0, str.Length - 1));

    // List to keep final string combinations
    List&lt;string&gt; finalArray = new List&lt;string&gt;();

    // add whatever is coming from the previous routine
    foreach (string s in returnArray)
        finalArray.Add(s);

    // take the last character
    finalArray.Add(c.ToString());

    // take the combination between the last char and the returning strings from the previous routine
    foreach (string s in returnArray)
        finalArray.Add(s + c);

    return finalArray.ToArray();
}
I can suggest following project for combinations and permutations which is very efficient and easy to use:

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

Then it's simple as:

IList&lt;Char&gt; chars = "abc".ToList();
List&lt;string&gt; allCombinations = new List&lt;String&gt;();
for (int i = 1; i &lt;= chars.Count; i++)
{ 
    var combis = new Facet.Combinatorics.Combinations&lt;Char&gt;(
        chars, i, Facet.Combinatorics.GenerateOption.WithRepetition);
    allCombinations.AddRange(combis.Select(c =&gt; string.Join("", c)));
}

foreach (var combi in allCombinations)
    Console.WriteLine(combi);


Output:

a
b
c
aa
ab
ac
bb
bc
cc
aaa
aab
aac
abb
abc
acc
bbb
bbc
bcc
ccc


If you don't want repetion you just have to change GenerateOption.WithRepetition to GenerateOption.WithoutRepetition and the result is:

a
b
c
ab
ac
bc
abc