216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii/

Python

Backtracking

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        options = [num for num in range(1, 10)]
        result = set()

        def backtrack(track: set):
            if len(track) == k:
                if sum(track) == n:
                    result.add(tuple(sorted(list(track))))
                return

            current_total = sum(track)

            for option in options:
                if option in track:
                    continue

                if current_total + option > n:
                    continue

                track.add(option)
                backtrack(track)
                track.remove(option)

        backtrack(set())

        return list(result)