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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Complete search

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

Solutions:
class Solution:

	def combinationSum3(self, k, n):
		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):
		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):
		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:
			return

	def combinationSum3(self, k, n):
		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):
		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):
		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):
		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]