Algorithm to generate all combinations of a string

Question

I found a link online that shows an algorithm to generate all combinations of a string: http://www.mytechinterviews.com/combinations-of-a-string

Algorithm is copied below.

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);

What I don't understand is the line:

outstr.deleteCharAt(outstr.length() - 1);

If I remove this line, the program obviously does not work anymore, but why is this needed in the first place? I understand the recursive idea where we vary an initial character and recurse on the remaining characters, but the deleteChar line does not seem to fit in logically anywhere. What was the reason for adding the outstr.deleteCharAt line?

Answer 1

Simplest way of calculating the possible combinations of strings is here ...

Mathematically to find R combinations in a given lot of N = NcR

So what we are finding here is, all possible combinations = Nc0 + Nc1 .... + Ncn = 2 Pow N

So you get 2 Pow N combinations for given word of length N characters.

If you represent 1 to (2 Pow N) integers in binary, and place your char in the place where 1 is present, finally you would get the solution.

Example:

Input : ABC

Solution :

ABC length is 3. So possible combinations 2 Pow 3 = 8

If 0 - 8 represented in binary

000 =

001 = C

010 = B

011 = BC

100 = A

101 = AC

110 = AB

111 = ABC

all possible combinations are shown above.

Answer 2

The call of outstr.deleteCharAt counters the effect of outstr.append by deleting the last character of the outstr.

Each loop iteration proceeds as follows:

1. append a character
2. print the result
3. perform a recursive invocation at the level i+1
4. remove the character we added at step 1