如何推导LeetCode 216回溯解法的时间复杂度？

问题回顾 #

从1-9中找出k个不同数字的组合，使其和为n，返回所有有效组合。你提供的回溯代码已验证正确，代码如下：

def combinationSum(k: int, n: int) -> list[list[int]]:
    def backtrack(res, start, cur, curSum):
        if len(cur) == k:
            if curSum == n:
                res.append(cur[:])
            return
        for i in range(start, 10):
            cur.append(i)
            backtrack(res, i + 1, cur, curSum + i)
            cur.pop()
    
    c = []
    backtrack(c, 1, [], 0)
    return c

时间复杂度推导 #

1. 核心逻辑：遍历所有k长度的组合

你的回溯算法本质是生成所有长度为k的严格递增数字组合（通过start = i+1保证不重复选取之前的数字），这些组合的总数对应组合数公式：
C(9, k) = 9! / (k! * (9 - k)!)
这是因为我们从9个数字中挑选k个不重复的数，且递增的选取方式避免了重复组合。

2. 递归调用的总次数

除了最终的k长度组合，递归过程中还会生成所有长度为1到k-1的中间组合，总递归调用次数为：
sum_{m=1}^k C(9, m)
比如k=3时，总调用次数是C(9,1)+C(9,2)+C(9,3) = 9+36+84=129次。

3. 每个组合的处理成本

• 对于长度小于k的中间组合，每次递归仅执行循环和入栈/出栈操作，时间成本为O(1)（每个步骤都是常数时间）。
• 对于长度等于k的最终组合：
  • 判断curSum == n是O(1)操作；
  • 如果符合条件，执行res.append(cur[:])需要复制当前长度为k的列表，时间成本为O(k)。

4. 最坏情况时间复杂度

当所有k长度的组合都满足和为n的条件时，时间复杂度由两部分主导：

• 生成所有组合的递归调用：O(sum_{m=1}^k C(9, m))
• 复制符合条件的组合到结果：O(C(9,k)*k)

由于C(9,k)*k的量级大于sum_{m=1}^{k-1} C(9,m)（比如k=5时，C(9,5)*5=126*5=630，而sum_{m=1}^4 C(9,m)=255），因此最坏情况下时间复杂度可简化为O(C(9,k)*k)。

关于“指数级”的说明

你提到的“指数级”是针对一般化场景而言：如果把问题扩展为从1到M中选k个数字（M是可变的大整数），那么组合数C(M,k)当k接近M/2时会呈指数增长（符合组合数的增长特性）。但在本题中，M固定为9，所有可能的组合数都是常数（最大为C(9,5)=126），所以实际运行时间是固定范围内的常数级，但从算法结构来看，它属于组合搜索类算法，这类算法在输入规模可变时通常表现为指数级复杂度。

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