Combination Sum III Python Solution with Tests

lcpy gen -n 216   # by problem number
lcpy gen -s combination_sum_iii   # by problem name

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

class Solution:
    # Time: O(C(9, k) * k)
    # Space: O(k) recursion depth (output excluded)
    def combination_sum_3(self, k: int, n: int) -> list[list[int]]:
        results: list[list[int]] = []
        combo: list[int] = []

        def backtrack(start: int, remaining: int) -> None:
            if len(combo) == k:
                if remaining == 0:
                    results.append([*combo])
                return
            for num in range(start, 10):
                if num > remaining:
                    break
                combo.append(num)
                backtrack(num + 1, remaining - num)
                combo.pop()

        backtrack(1, n)
        return results