如何计算从列表中找出指定值所有和组合的函数的时间复杂度？

首先明确你的代码逻辑：这是一个无重复选取元素的组合求和算法（通过start参数控制每次递归只从当前元素的下一个位置开始选择，避免生成重复组合），核心递归函数Mystery负责遍历所有符合条件的组合。

你的递归式问题 #

你之前推导的递归式存在两个关键问题：

1. 参数定义模糊：T(n,x)未明确是处理前n个元素还是从某个起始位置到末尾的元素，导致递归分支的参数对应关系错误；
2. 递归分支的剩余元素数计算错误：每次选择A[i]后，下一层递归的剩余元素数是n - (i+1)（从i+1到末尾的元素数量），而非n-i。

正确的递归式推导 #

我们重新定义递归函数的参数：设T(k, t)表示处理k个连续元素（当前递归层的start到末尾共k个元素）、剩余目标和为t时的时间复杂度。

基准情况 #

• 当t == 0：只需将当前组合加入结果，时间复杂度为O(1)；
• 当t < 0或k == 0：直接返回，时间复杂度为O(1)。

递归情况 #

对于当前层的k个元素，我们依次选择第i个元素（i从0到k-1，对应原数组的start+i位置），然后递归处理剩下的k-i-1个元素，剩余目标和变为t - A[start+i]。因此递归式为：

T(k, t) = O(1) + Σ（i=0到k-1）T(k - i - 1, t - A[start+i])

这里的O(1)是当前层循环的初始化、条件判断等固定开销。

最坏时间复杂度分析 #

最坏情况出现在所有元素均为正数，且目标和x大于等于所有元素的总和时——此时算法会遍历所有可能的非空子集（每个元素有选或不选两种可能，但通过start避免了重复组合）。

• 若所有元素为1且x >= n，总共有2^n - 1个非空子集，每个子集都会被递归处理，时间复杂度为O(2^n)；
• 一般情况下，当元素均为正数时，时间复杂度的上界为O(2^n)，因为每个元素最多被选一次，总共有2^n种可能的子集组合。

另外，主函数中的A.sort()时间复杂度为O(n log n)，但当n较大时，O(2^n)远大于O(n log n)，因此整体时间复杂度由递归部分主导，即O(2^n)。

补充说明 #

如果数组中存在重复元素，你的代码会生成重复的组合（因为排序后相同元素会被多次选择），但这不影响时间复杂度的上界分析——最坏情况下依然是O(2^n)。

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