给定字符列表生成顺序非空字符串的时间与空间复杂度是多少

你要生成的其实是原字符序列所有长度≥1的子序列，子序列的核心要求就是保持原序列元素的相对顺序，允许跳过任意个中间元素，和你给出的规则完全匹配。你示例的输出其实漏了wxz和单个z两个结果，完整符合规则的4元素输入输出总共有15个，正好对应2^4 -1的总数。

生成规律说明 #

对于长度为n的输入列表：

• 每个元素都有「被选入当前子序列」和「不被选入」两种独立选择，排除所有元素都不选的空序列，总共有 2^n - 1 个符合要求的子序列
• 如果固定从第i个元素（下标从0开始）作为子序列的第一个元素，那么它后面的n-i-1个元素每个都可选可不选，所以以第i个元素开头的子序列总数为 2^{n-i-1} 个，所有起点的子序列加起来正好是 2^n - 1 个，和总数量完全对应

时间复杂度计算 #

时间复杂度需要覆盖所有子序列的生成和输出成本：

• 所有子序列的总字符数为 sum_{k=1}^n k*C(n,k) = n*2^{n-1}，其中C(n,k)是从n个元素中选k个的组合数
• 不管用递归回溯还是迭代法生成，每个字符都需要至少一次写入/遍历操作，所以整体时间复杂度为 O(n*2^n)

空间复杂度计算 #

空间复杂度分两种场景说明：

• 包含输出结果的总空间：需要存储所有2^n -1个子序列，总字符数和上述计算一致，为O(n*2^n)
• 仅计算额外辅助空间：如果用回溯法实现，递归栈的最大深度是n，临时存储当前正在生成的子序列的空间最多也是n；如果用迭代法实现，辅助空间同样只需要O(n)，所以额外辅助空间复杂度为O(n)

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