How can I find the time complexity of this algorithm (backtracking)?

Question

This is a function I wrote in Python for Leetcode 216. The problem statement is:

Find all combinations of k distinct digits from [1-9] s.t they sum to n. Return a list of all valid combinations, knowing that 2 <= k <= 9, 1 <= n <= 60

This is my algorithm:

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

and it is correct. I am having trouble with the time complexity though. I understand it is exponential, but how can I go about deducing it?

Answer 1

It is actually:

Why?:

• Each time you pick upto k distinct digits out of 9 available ones. (I think it is already clear to you as per your comment)
• The base case always starts with [i] (single sized cur) up to [i, i+1,...] (k sized cur)
  • Therefore, all the k th iterations of backtrack includes 1 to (k-1)th generations (9C1 + 9C2 + ... + 9Ck)