我怎样才能找到这个算法的时间复杂度（回溯）？

Question

这是我用 Python 为 Leetcode 216 编写的函数。问题陈述是：

从 [1-9] 中找到 k 个不同数字的所有组合，它们的总和为 n。返回所有有效组合的列表，已知 2 <= k <= 9, 1 <= n <= 60

这是我的算法：

def combinationSum(k: int, n: int) -> list[list[int]]:

        def backtrack(res, start, cur, curSum):
            print(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

这是正确的。不过，我在时间复杂度方面遇到了麻烦。我知道它是指数的，但是我怎样才能推导出它呢？

Answer 1

其实是：

为什么？：

• 每次您从 upto

   可用数字中选择 

  k

  9

  不同的数字。 （我想根据你的评论你已经很清楚了）
• 基本情况始终从

  [i]

  （单一尺寸

  cur

  ）开始到

  [i, i+1,...]

  （

  k

  尺寸

  cur

  ）
  • 因此，

    n

    的所有第

    backtrack

    迭代包括

    1 to (n-1)th

    代(

    9C1 + 9C2 + ... + 9Ck

    )