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

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 行的原因是什么？

原文由 john 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

调用 outstr.deleteCharAt outstr.append 通过删除 --- 的最后一个字符来 outstr 的影响。

每个循环迭代过程如下：

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

原文由 Sergey Kalinichenko 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

计算可能的字符串组合的最简单方法是在这里……

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

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

因此，对于长度为 N 个字符的给定单词，您会得到 2 个 Pow N 组合。

如果你用二进制表示 1 到 (2 Pow N) 整数，并将你的字符放在 1 出现的地方，最后你会得到解决方案。

例子：

输入：ABC

解决方案 ：

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

如果 0 - 8 以二进制表示

000 =

001 = C

010 =乙

011=公元前

100 = 一个

101 = 交流电

110 = AB

111 = 美国广播公司

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

原文由 Sunil 发布，翻译遵循 CC BY-SA 3.0 许可协议