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.

7 Responses

  1. 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);
    }
    }

  2. dede says:

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

  3. 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;
    }

  4. 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));
    combinations.add(outstr.toString());
    combinations.addAll(getCombinations(instr, outstr, i + 1));
    outstr.deleteCharAt(outstr.length() – 1);
    }
    return combinations;
    }

  5. 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?

  6. 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)

  7. JM says:

    Above algorithm generates repeats. Ex, input string is aaa

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

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