# Combinations of a String

Question: Write an algorithm to print all possible combinations of characters in a string.

Answer: Any thoughts? One thing is for sure, we can definitely use some recursive logic here. Let’s approach this problem methodically. Since we need to generate combinations, we can start with a single character and then continue to add a character to combinations we have seen so far. Let’s use “abc” as an example.

Here’s some code in Java (for a change :)) to achieve what we’ve described above.

```void combine(String instr, StringBuffer outstr, int index)
{
for (int i = index; i < instr.length(); i++)
{
outstr.append(instr.charAt(i));
System.out.println(outstr);
combine(instr, outstr, i + 1);
outstr.deleteCharAt(outstr.length() - 1);
}
}

combine("abc", new StringBuffer(), 0);```

Have a better solution? Please let us know through the comments section.

If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:  ## 10 Responses

1. sandip says:

int main()
{
char x;
printf(“\nEnter a word : “);
scanf(“%s”,x);
permutate(x,0,strlen(x)-1);
return 0;
}
void permutate(char *x,int i,int n)
{
int j;
if(i==n)
printf(“%s”,x);
else
{
for(j=i;j<=n;j++)
{
swap(x+i,x+j);
permutate(x,i+1,n);
swap(x+i,x+j);
}
}
}
void swap(char *x,char *y)
{
char temp;
temp=*x;
*x=*y;
*y=temp;
}

2. sandip says:

here is another solution…

3. Vladimir says:

Because there are n! possible combinations (permutations) of a string, any algorithm that claims to do it in less time is probably wrong.

Here’s a solution, in JavaScript-ish pseudocode (works in a language with mutable strings):

function anagrams(inStr) {
_anagrams(inStr, 0);
}

function _anagrams(inStr, fromIndex) {
var temp;
if (fromIndex == inStr.length) {
print(inStr);
} else {
for (var i = fromIndex; i < inStr.length; i++)
{
temp = inStr[fromIndex];
inStr[fromIndex] = inStr[i];
inStr[i] = temp;
_anagrams(inStr, fromIndex + 1);
inStr[i] = inStr[index];
inStr[fromIndex] = temp;
}
}
}

4. Atul says:

Here’s my implementation. I thought the original solution was not correct and it was not printing all the possible combinations of characters in string. This solution is O(n^2):
``` private void printCombinations(String string) { for (int i = 0; i 0) { substr = string.substring(0, i); } substr += string.substring(i + 1); combine(substr,string.charAt(i)); } }```

``` ```

``` private void combine(String instr, char first) { String rotate = instr; for (int i = 0; i < instr.length(); i++) { System.out.println(first + rotate); if (i < (instr.length() - 1)) { rotate = instr.substring(i+1); } rotate += instr.substring(0, i+1); } } ```

5. dede says:

Can some one give me the complexity of such an algorithm ?

6. mhassan83 says:

``` Set getCombinations(String instr, StringBuffer outstr, int index) { Set combinations = new HashSet(); for (int i = index; i < instr.length(); i++) { outstr.append(instr.charAt(i)); combinations.add(outstr.toString()); combinations.addAll(getCombinations(instr, outstr, i + 1)); outstr.deleteCharAt(outstr.length() - 1); } return combinations; } ```

7. mhassan83 says:

I would recommend few improvement in the code to avoid invalid combinations (duplicates)

Set getCombinations(String instr, StringBuffer outstr, int index)
{
Set combinations = new HashSet();
for (int i = index; i < instr.length(); i++)
{
outstr.append(instr.charAt(i));
outstr.deleteCharAt(outstr.length() – 1);
}
return combinations;
}

8. andy says:

did you try running that code? it doesn’t print out quite a number of combinations (e.g. “cba”, “cab”, etc). What gives?

9. abbulu says:

Other solution is multi the characters in each string with integer values and 256. Then sort the values and compare values next to each if any two numbers equals then corresponding strings are anagrams. O(n)+O(nlogn)+O(n)

10. JM says:

Above algorithm generates repeats. Ex, input string is aaa

XHTML: These are some of the tags you can use: `<a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>`