Leetcode 216 Combination Sum III

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.

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. [1,2,1] is not valid because 1 is used twice.

Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.

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

• Soruda bize k ve n sayıları veriliyor.1-9 arası rakamların kombinasyonlarını kullanarak n sayısını bulmamız isteniyor.k kombinasyonda kaç rakam kullanabiliriz n sayısı ise bu rakamların toplamı olan sayı.Ve 1-9 arası rakamları sadece bir kere kullanabiliriz.
• n = 3 k = 7 olsun bu durumda cevap sadece (1,2,4) olur.Sadece bu kombinasyonun sonucu 7 sayısını verir.
• Oluşturacağımız backtrack fonksiyonunu rekürsif olarak çağırarak kombinasyonları arayabiliriz.
• İlk olarak (1) buluruz sonrasında (1,2),(1,3),(1,4)… (1,9) alt çağrılarını yaparız.Devamında bu kollarda (1,2,3),(1,2,4),(1,2,5) şeklinde devam eder.

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []
        def backtrack(remain, comb, next_start):
            if remain == 0 and len(comb) == k:
                # make a copy of current combination
                # Otherwise the combination would be reverted in other branch of backtracking.
                results.append(list(comb))
                return
            elif remain < 0 or len(comb) == k:
                # exceed the scope, no need to explore further.
                return

            # Iterate through the reduced list of candidates.
            for i in range(next_start, 9):
                comb.append(i+1)
                backtrack(remain-i-1, comb, i+1)
                # backtrack the current choice
                comb.pop()

        backtrack(n, [], 0)

        return results