使用'_'与'+'两种连接符生成数组元素全组合的算法求解

先从你给出的示例反推出准确的生成规则，放在最前面避免算法写偏：

• 数组第一个元素（索引为0的元素）永远固定在结果字符串的最开头，位置不会变动
• 剩下的所有元素（索引1到n-1）可以任意分配到不同分组，第一个分组必须包含索引0的元素
• 分组和分组之间用+连接，同一个分组内的元素按索引从小到大排序，元素之间用_连接
• 所有合法分配方式对应的字符串，就是需要的全部结果

校验：n=2时总共有2种结果、n=3时总共有5种结果，和你给出的示例数量完全匹配；n=4、n=5下列出的示例条目也全部符合这个规则，没有反例。本质这就是数学上的集合划分问题，结果总数对应第n个贝尔数。

不用写复杂递归，用增量生成的方法实现即可，逻辑简单不容易出bug，步骤如下：

1. 初始化状态列表。最开始还没处理后续元素，只有一个包含索引0元素的分组，比如数组是[0,1,2]，初始状态就是[[0]]（每个子列表代表一个分组，存分组内的元素值）
2. 按索引从小到大逐个处理剩下的元素（从索引1一直到最后一个元素），对每一个新拿到的元素，基于上一轮生成的所有状态扩展出新状态：对每个已有的状态，新元素有两类合法选择：
   • 把新元素追加到这个状态下任意一个已有分组的末尾（因为新元素的索引比之前处理过的都大，直接追加就满足分组内按索引升序的要求，不需要额外排序）
   • 给新元素单独建一个新分组，追加到分组列表的最后
3. 每处理完一个元素，就用新生成的状态列表替换旧的，进入下一轮处理
4. 等所有元素都处理完，把每个最终状态转换成字符串即可：每个分组内的元素用_连接，不同分组之间用+连接。

跟着走一遍就能明确逻辑：

1. 处理完0之后，状态列表只有1个状态：[[0]]
2. 处理元素1：
   • 把1追加到现有唯一分组，得到新状态[[0,1]]
   • 给1建新分组，得到新状态[[0], [1]]
     此时状态列表共2个状态
3. 处理元素2，对上面2个状态分别扩展：
   • 对状态[[0,1]]：
     • 2追加到现有分组：得到[[0,1,2]]，转字符串是0_1_2
     • 2建新分组：得到[[0,1], [2]]，转字符串是0_1+2
   • 对状态[[0], [1]]：
     • 2追加到第一个分组：得到[[0,2], [1]]，转字符串是0_2+1
     • 2追加到第二个分组：得到[[0], [1,2]]，转字符串是0+1_2
     • 2建新分组：得到[[0], [1], [2]]，转字符串是0+1+2
       最终正好5个结果，和你给出的n=3示例完全一致，没有遗漏也没有多余项。

• 扩展新状态的时候，记得对原状态做结构拷贝，不要直接修改原状态，不然会导致不同状态之间互相污染
• 不需要额外做排序操作，因为是按索引从小到大处理元素，追加到分组末尾天然满足分组内升序的要求，能省掉不必要的开销
• 这个方法的时间复杂度和结果总数线性相关，属于最优实现，毕竟本身就要输出所有结果，没有多余计算。

内容的提问来源于stack exchange，提问作者richin