[LeetCode] 216. Combination Sum III

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

Use backtracking approach. Pick up one number at a time until find a valid combination, then it into the result bucket.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        result = []
        
        def backtracking(start, sums, partial):
            if len(partial) == k and sums == n:
                result.append(partial)
                return
            
            for i in range(start, 10):
                if sums + i <= n:
                    backtracking(i+1, sums+i, partial + [i])
        
        backtracking(1, 0, [])
        return result