Combination Sum III Python Solution with Tests

Tested Python solution for LeetCode 216 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 216, Medium. Topics: Array, Backtracking. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 22 parametrized pytest cases, and a playground notebook:

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

​

Problem

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

​

Examples

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.

​

Constraints

• 2 <= k <= 9
• 1 <= n <= 60

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

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

​

Complexity

Time	Space
O(C(9, k) * k)	O(k) recursion depth (output excluded)

​

Tags