求数组指定长度k的所有子集的递归程序的时间复杂度

你的实现思路是通过逐层删除当前数组的元素，直到数组长度等于目标k时将其加入结果集，所有递归调用都嵌套在遍历当前数组元素的for循环内。首先注意你的代码存在一个小问题：subsets函数没有显式返回值，所以result永远是None，if not result in finalarr and result:这段逻辑实际永远不会执行，属于无效代码，计算复杂度时可以忽略。

核心递归的调用规模计算 #

• 设原始数组长度为n，递归的深度固定为n - k：每进入一次递归，当前数组长度会减少1，直到长度等于k时触发终止条件返回。
• 不考虑重复路径的情况下，各层递归的总调用次数如下：
  • 第1层（当前数组长度为n）：共触发n次递归
  • 第2层（当前数组长度为n-1）：共触发n * (n-1)次递归
  • ...
  • 第n-k层（当前数组长度为k+1）：共触发n * (n-1) * ... * (k+1) = n!/k!次递归

单次递归的操作开销 #

• 每次递归内的数组拷贝n[:]、元素删除aux.remove(i)操作，时间复杂度都和当前数组长度成正比，最高为O(n)
• 终止条件里的存在性判断if not n in finalarr需要遍历当前所有已存储的结果做数组比对，单次比对开销为O(k)，最坏情况下结果集大小为组合数C(n,k)，这部分会带来额外的开销

最终Big O上界 #

• 不考虑存在性判断的额外开销时，核心递归逻辑的最坏时间上界为 O(n * n!/k!)
• 算上存在性判断的最坏开销时，整体时间上界为 O(n! * C(n,k))（C(n,k)为从n个元素选k个的组合数）

相关疑问解答 #

你认为可以提前终止所以不存在theta界的理解是不准确的：我们计算Big O时取的是最坏情况的上界，你代码里的终止条件是固定触发的，不属于随机的提前跳出逻辑，最坏情况下所有可能的递归路径都会走完，因此是存在确定的上界的。

另外你的实现存在大量重复递归路径的问题：比如先删元素A再删元素B和先删B再删A最终得到的数组是相同的，这部分重复计算拉高了时间复杂度。如果改为用下标指针按顺序选元素，避免走重复路径，时间复杂度可以降到更优的O(k * C(n,k))，仅和实际的子集数量成正比。

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