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]]

Difficulty: interview

Starter code:

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        

Solutions:
class Solution:
     def combinationSum3(self, k, n):
         """
         :type k: int
         :type n: int
         :rtype: List[List[int]]
         """
         to_return = []
         self.backtrack(to_return, [], k, n, 1)
         return to_return
     
     def backtrack(self, to_return, temp, k, n, start):
         total = sum(temp)
         
         if total > n:
             return
         if len(temp) == k and total == n:
             to_return.append(temp[:])
             return
         
         for i in range(start, 10):
             temp.append(i)
             self.backtrack(to_return, temp, k, n, i + 1)
             temp.pop()

class Solution:
     def combinationSum3(self, k, n):
         """
         :type k: int
         :type n: int
         :rtype: List[List[int]]
         """
         res = []
         self.dfs(range(1,10), k, n, 0, [], res)
         return res
 
     def dfs(self, nums, k, n, index, path, res):
         if k == 0 and n == 0:
             res.append(path)
             return 
         for i in range(index, len(nums)):
             self.dfs(nums, k-1, n- nums[i], i + 1, path+[nums[i]], res)

class Solution:
     def combinationSum3(self, k, n):
         """
         :type k: int
         :type n: int
         :rtype: List[List[int]]
         """
 
         res = []
         temp = []
         idx = 1
         self.backtracking(res, temp, n, k, idx)
         
         return res
     
     def backtracking(self, res, temp, n, k, idx):
         if len(temp) == k and n == 0:
             res.append(temp[:])
             return
         
         for i in range(idx, 10):
             temp.append(i)
             self.backtracking(res, temp, n - i, k, i + 1)
             temp.pop()
             


class Solution:
     def combinationSum3(self, k, n):
         res, com = [], []
         self.combination(n, res, com, 1, k)
         return res
     
     def combination(self, target, res, com, begin, k):
         for i in range(begin, target + 1 if target < 9 else 10):
             com.append(i)
             if i == target and k == 1: res.append(com[:])
             self.combination(target - i, res, com, i + 1, k - 1)
             com.pop()


class Solution:
     result = []
     def combinationSum3Util(self, candidates, current_subset, k, target, start):
         if target == 0 and k == 0:
             Solution.result.append(current_subset)
         
         elif target != 0 and k != 0:
             for i in range(start, len(candidates)):
                 current_candidate_num = candidates[i]
                 if i > start and candidates[i] == candidates[i-1]:
                     continue
                     
                 if target - current_candidate_num >= 0:
                     next_subset = current_subset.copy()
                     next_subset.append(current_candidate_num)
                     self.combinationSum3Util(candidates, next_subset, k-1, target - current_candidate_num, i+1)
                 else:
                     return
         
         else:   # target == 0 and k != 0     OR     target != 0 and k == 0
             return
                 
     def combinationSum3(self, k, n):
         """
         :type k: int
         :type n: int
         :rtype: List[List[int]]
         """
         Solution.result = []
         
         if k == 0:
             return [[]]
         
         candidates = [x for x in range(1, 10)]
         current_subset = []
         self.combinationSum3Util(candidates, current_subset, k, n, 0)
         return Solution.result


class Solution:
     def combinationSum3(self, k, n):
         """
         :type k: int
         :type n: int
         :rtype: List[List[int]]
         """
         
         if(n > 45): return []
         res = []
         def rev(start, s, count, one):
             if(count == k and s == n):
                 res.append(one[:])
                 return
             if(count == k or s == n):
                 return
             for i in range(start, 10):
                 if(s + i > n): return
                 rev(i+1, s+i, count+1, one+[i])
         rev(1, 0, 0, [])
         return res

class Solution:
     def combinationSum3(self, k, n):
         """
         :type k: int
         :type n: int
         :rtype: List[List[int]]
         """
         res = []
         self.dfs(res, [], 0, 0, 1, k, n)
         return res
     
     def dfs(self, res, cur, d, s, b, k, n):
         if d == k and s == n:
             res.append(cur)
             return
         
         for i in range(b, 10):
             self.dfs(res, cur + [i], d + 1, s + i, i + 1, k, n)

class Solution:
     def combinationSum3(self, k, n):
         """
         :type k: int
         :type n: int
         :rtype: List[List[int]]
         """
         import functools;
         return [ c for c in functools.reduce(lambda nexts, _ : [next_+[first] for next_ in nexts for first in range(next_[-1]+1 if next_ else 1, 10)], range(k), [[]]) if sum(c) == n]