递归地拼出一个单词

Question

我得到了这个:

编写一个递归程序,给定一个没有空格的字符串,将其分解为字符串的每个可能的分段为"单词".也就是说,打印出每个可能的字符串版本,并在其中插入空格.给出分段字符串的顺序无关紧要,但必须给出所有可能的分段,不重复.

如果有人可以提供帮助,我将完全失去如何开始.

输出应该如下所示:

 Enter a string: ABCD

 ABCD
 A BCD
 A B CD
 A B C D
 A BC D
 AB CD
 AB C D
 ABC D

Answer 1

您已经给出了输出的模式(如,按照产生这些输出的顺序).考虑2-5的输出有什么共同点:

A BCD
A B CD
A B C D
A BC D

因此,看起来您的函数将打印其input(ABCD),然后它将第一个字母作为前缀(A),并递归地查找其余字母(BCD)的所有组合.这将暗示函数的实际定义有两个参数 - 一个已经扩展的前缀,以及一组枚举组合的剩余字母.

用一个字母完成后,我们将另一个字母移到这个前缀(AB)中,然后递归地找到剩余字母(CD)的所有组合,以产生下一组输出:

AB CD
AB C D

Answer 2

我会给你提示帮助:

想想如何递归地解决这个问题.基本上,这可以通过"分而治之"的变化来解决.对于给定长度为n的字符串,有n-1个位置可以插入分隔符空格.

因此,如果您有一个长度为2的字符串,则有一个位置可以插入分隔符,还有两个变体:是否插入分隔符.

如果您有一个长度为3的字符串,则您在2个位置有2个选项.因此,该函数可以创建一个首先插入空格的字符串,并使用字符串的未处理尾部递归调用自身,以生成该子字符串的所有变体.然后创建另一个前缀字符串,其中第一个位置没有插入空格,并再次使用字符串的其余部分调用自身.

对于每个递归调用,它需要传递已经生成的字符串前缀以及字符串的剩余未处理尾部.