Combination Sum III

combination_sum_iii.py

"""
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used
and each combination should be a unique set of numbers.

Note:
All numbers will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
"""
from itertools import combinations
from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        self.dfs(list(range(1, 10)), k, n, [], res)
        return res

    def dfs(
        self, nums: List[int], k: int, n: int, path: List[int], res: List[int]
    ) -> List[List[int]]:
        if k < 0 or n < 0:
            return res
        if k == 0 and n == 0:
            res.append(path)
        for i in range(len(nums)):
            self.dfs(nums[i + 1 :], k - 1, n - nums[i], path + [nums[i]], res)

    def combinationSum3Library(self, k: int, n: int) -> List[List[int]]:
        return [c for c in combinations(range(1, 10), k) if sum(c) == n]