生成字符串的所有组合的算法

Question

我在网上找到了一个链接,显示了生成字符串所有组合的算法:http://www.mytechinterviews.com/combinations-of-a-string

算法复制如下.

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

我不明白的是这条线:

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

如果我删除这一行,该程序显然不再起作用,但为什么首先需要它？我理解递归的想法,我们改变一个初始字符并递归剩余的字符,但deleteChar行似乎在逻辑上不适合任何地方.添加outstr.deleteCharAt行的原因是什么？

Answer 1

计算字符串可能组合的最简单方法是......

在数学上找到给定批次的N = NcR中的R组合

所以我们在这里发现的是,所有可能的组合= Nc0 + Nc1 .... + Ncn = 2 Pow N.

因此,对于长度为N个字符的给定单词,您将获得2个Pow N组合.

如果用二进制表示1到(2 Pow N)整数,并将char放在1所在的位置,最后你会得到解决方案.

例:

输入:ABC

方案:

ABC长度为3.因此可能的组合2 Pow 3 = 8

如果0 - 8以二进制表示

000 =

001 = C.

010 = B.

011 = BC

100 = A.

101 = AC

110 = AB

111 = ABC

所有可能的组合如上所示.

Answer 2

通过删除最后一个字符来调用outstr.deleteCharAt计数器的效果.outstr.appendoutstr

每个循环迭代过程如下:

1. 追加一个角色
2. 打印结果
3. 在该级别执行递归调用 i+1
4. 删除我们在步骤1中添加的字符