# 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 };

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<string> finalArray = new List<string>();

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

// take the last character

// take the combination between the last char and the returning strings from the previous routine
foreach (string s in returnArray)

return finalArray.ToArray();
}

• For big strings you can fall through stackoverflow exception. – Hamlet Hakobyan Jul 8 '13 at 7:07
• @HamletHakobyan: thanks for your reply. is there any way to avoid it? – Pritam Karmakar Jul 8 '13 at 7:15
• @p.s.w.g: From next time I will surely post such question in the codereview site. thanks for the information. – Pritam Karmakar Jul 8 '13 at 7:16

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<Char> chars = "abc".ToList();
List<string> allCombinations = new List<String>();
for (int i = 1; i <= chars.Count; i++)
{
var combis = new Facet.Combinatorics.Combinations<Char>(
chars, i, Facet.Combinatorics.GenerateOption.WithRepetition);
}

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

• I wonder if that would be accepted at an interview. – svick Jul 8 '13 at 14:14

You can improve the implementation by building the strings only when needed:

public static string[] Combination2(string str)
{
List<string> output = new List<string>();
// Working buffer to build new sub-strings
char[] buffer = new char[str.Length];

Combination2Recurse(str.ToCharArray(), 0, buffer, 0, output);

return output.ToArray();
}

public static void Combination2Recurse(char[] input, int inputPos, char[] buffer, int bufferPos, List<string> output)
{
if (inputPos >= input.Length)
{
if (bufferPos > 0)

return;
}

// Recurse 2 times - one time without adding current input char, one time with.
Combination2Recurse(input, inputPos + 1, buffer, bufferPos, output);

buffer[bufferPos] = input[inputPos];
Combination2Recurse(input, inputPos + 1, buffer, bufferPos + 1, output);
}


When run 100,000 times with the string 'abcdefghi' on my laptop the results are:

• Question's implementation: 5.21s
• This implementation: 2.48s
• Tim Schmelter's implementation: 93s
• p.s.w.g's implementation: 142s

You can further improve performance/memory by pre-allocating the needed output array string[] and writing the strings directly to the array (the size is 2^n, minus 1 the empty string).

• Just wondering, is the Tim you referring now Rango? – Chor Wai Chun Apr 29 '19 at 5:52
• @ChorWaiChun Yes. – sagis Apr 30 '19 at 19:51

Mostly for fun, this version will work for strings up to 30 characters long:

var str = "abc";
var results =
from e in Enumerable.Range(0, 1 << str.Length)
let p =
from b in Enumerable.Range(0, str.Length)
select(e & (1 << b)) == 0 ? (char?)null : str[b]
select string.Join(string.Empty, p);


Or in fluent syntax:

var results = Enumerable.Range(0, 1 << str.Length)
.Select(e => string.Join(string.Empty, Enumerable.Range(0, str.Length).Select(b => (e & (1 << b)) == 0 ? (char?)null : str[b])));


The output will be:

{empty string}
a
b
ab
c
ac
bc
abc


You can use Enumerable.Range(1, (1 << str.Length) - 1) or .Skip(1) to exclude the empty string in the results.

If you write your own Range function using BigInteger's, like this:

public IEnumerable<BigInteger> Range(BigInteger start, BigInteger count)
{
while(count-- > 0)
{
yield return start++;
}
}


You can extend this technique to support strings of any length:

var results =
from e in Range(0, BigInteger.Pow(2, str.Length))
let p =
from b in Enumerable.Range(1, str.Length)
select(e & BigInteger.Pow(2, b - 1)) == 0 ? (char?)null : str[b - 1]
select string.Join(string.Empty, p);

• what about using UInt64 instead of int (as the data type of 'e' above) to work for strings of length up to 63 characters? – bytefire Jul 8 '13 at 9:07
• @bytefire Absolutely. You could do that, but you'd have to write your own version Enumerable.Range for that, which kind of ruins the nice 'one-liner' aspect of this solution, and ultimately it just pushes the hard limit back a few steps. If you use BigInteger's it will work for arbitrary-length strings (see my updated answer), though not as efficiently since BigInteger math is much slower than int or long math. – p.s.w.g Jul 8 '13 at 10:04
• My up vote was, in part, for the one-liner niceness. – bytefire Jul 8 '13 at 10:25
• I'm working on similar function and this gives a good head start, do you have any idea what I should change if I only wanted to find "connected" permutations in "original sequence"? For example, for the case of abc, the result should be only a/b/c/ab/bc/abc. – Chor Wai Chun Apr 29 '19 at 9:31
• @ChorWaiChun I think I'd take a different approach. In that case, each result would be a non-empty substring of str, i.e. from i in Range(0, str.length - 1) from j in Range(1, str.length - i) select str.Substring(i, j); – p.s.w.g Apr 29 '19 at 15:06