Find all valid combinations of K numbers that sum upto to N such that the following conditions are true:
	Only number 1 through 9 are used.
	Each number is used atmost once.
Return the list of all possible valid combinations.
Note: The list must not contain the same combination twice, and the combinations returned in any order.
 
Example 1:
Input:
K = 3
N = 7
Output: { {1, 2, 4} }
Explanation: 
1+ 2+ 4 = 7
There are no other valid combinations.
 
Example 2:
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.
 
Example 3:
Input:
K = 4
N = 3
Output: { { } }
Explanation: There are no valid combinations.
Using 4 different numbers in the range {1, 9}, the smallest sum we can get is 1 + 2 + 3 + 4 = 10 and since 10 > 3, there are no valid combinations.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function combinationSum() which takes the integers K and N as parameters and returns a list of all possible valid combinations.
Expected Time Complexity: O(2^{K})
Expected Auxiliary Space: O(K)
Constraints:
1 ≤ K ≤ 9
^{1 }≤ N_{  }≤ 60

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def combinationSum(self, K, target):

        # Code here

Solutions:
def combisum2(i, target, subs, arr, ans, n, num, k):
	if i == n:
		if target == 0 and k == num:
			ans.append(subs[:])
		return
	if target - arr[i] >= 0:
		subs.append(arr[i])
		num += 1
		combisum2(i + 1, target - arr[i], subs, arr, ans, n, num, k)
		num -= 1
		subs.pop()
	while i < n - 1 and arr[i] == arr[i + 1]:
		i += 1
	combisum2(i + 1, target, subs, arr, ans, n, num, k)

class Solution:

	def combinationSum(self, k, N):
		candidates = []
		for i in range(9):
			candidates.append(i + 1)
		ans = []
		subs = []
		i = 0
		num = 0
		combisum2(i, N, subs, candidates, ans, 9, num, k)
		return ans


class Solution:

	def solve(self, k, n, start, target, curr):
		if k == n and target == 0:
			self.ans.append(curr.copy())
			return
		if target < 0 or k > n:
			return
		for i in range(start, 10):
			curr.append(i)
			self.solve(k + 1, n, i + 1, target - i, curr)
			curr.pop()

	def combinationSum(self, K, target):
		self.ans = []
		self.solve(0, K, 1, target, [])
		return self.ans


class Solution:

	def combinationSum(self, k, target):

		def helper(i, k, sumtill):
			if k == 0:
				if sumtill == target:
					ans.append(subset.copy())
					return
			if sumtill > target:
				return
			if i > 9:
				return
			sumtill += i
			subset.append(i)
			helper(i + 1, k - 1, sumtill)
			sumtill -= i
			subset.pop()
			helper(i + 1, k, sumtill)
		ans = []
		subset = []
		sumtill = 0
		helper(1, k, sumtill)
		return ans


class Solution:

	def combsum(self, k, arr, index, seq, target):
		if k == 0:
			if target == 0:
				self.res.append(seq)
			return
		if index == len(arr):
			return
		self.combsum(k - 1, arr, index + 1, seq + [arr[index]], target - arr[index])
		self.combsum(k, arr, index + 1, seq, target)

	def combinationSum(self, K, target):
		self.res = []
		self.combsum(K, list(range(1, 10)), 0, [], target)
		return self.res


class Solution:

	def combinationSum(self, K, target):
		nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		(arr, combinations) = ([], [])
		self.noOfCombinations(0, target, arr, combinations, nums, K)
		return combinations

	def noOfCombinations(self, n, target, arr, combinations, nums, k):
		if target == 0 and len(arr) == k:
			temp = [ele for ele in arr]
			combinations.append(temp)
			return
		if n == len(nums):
			return
		if nums[n] <= target:
			arr.append(nums[n])
			self.noOfCombinations(n + 1, target - nums[n], arr, combinations, nums, k)
			arr.pop()
		self.noOfCombinations(n + 1, target, arr, combinations, nums, k)


class Solution:

	def combinationSum(self, K, target):
		res = []
		ds = []
		ans = []
		for i in range(1, 10):
			ds.append(i)

		def getAns(ind, tar, ds, ans, res):
			if ind == len(ds):
				if len(ans) == K and tar == 0:
					res.append(ans[:])
				return
			if ds[ind] <= tar:
				ans.append(ds[ind])
				getAns(ind + 1, tar - ds[ind], ds, ans, res)
				ans.pop()
			getAns(ind + 1, tar, ds, ans, res)
		getAns(0, target, ds, ans, res)
		return res


class Solution:

	def combinationSum(self, k, target):
		arr = [i for i in range(1, 10)]
		res = []

		def backtrack(subset, idx, sum, count):
			if count == k and sum == target:
				res.append(subset[:])
				return
			if idx >= len(arr) or count > k or target < 0:
				return
			subset.append(arr[idx])
			backtrack(subset, idx + 1, sum + arr[idx], count + 1)
			subset.pop()
			backtrack(subset, idx + 1, sum, count)
		backtrack([], 0, 0, 0)
		return res


class Solution:

	def gen(self, k, target, nums, arr, brr, pos, c):
		if pos == 9 or c == k:
			if target == 0 and c == k:
				crr = brr.copy()
				arr.add(tuple(crr))
			return
		if target < 0:
			return
		brr.append(nums[pos])
		self.gen(k, target - nums[pos], nums, arr, brr, pos + 1, c + 1)
		brr.pop()
		self.gen(k, target, nums, arr, brr, pos + 1, c)

	def combinationSum(self, K, target):
		nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		arr = set()
		brr = []
		self.gen(K, target, nums, arr, brr, 0, 0)
		return sorted(list(arr))


from itertools import combinations

class Solution:

	def combinationSum(self, K, target):
		ans = []
		arr = range(1, 10)
		comb = combinations(arr, K)
		for i in comb:
			if sum(i) == target:
				ans.append(i)
		return ans


class Solution:

	def combinationSum(self, K, target):
		from itertools import combinations
		l = []
		c = combinations(range(1, 10), K)
		s = []
		for i in c:
			if sum(i) == target:
				s.append(i)
		return s


class Solution:

	def combinationSum(self, k, n):
		ans = []

		def dfs(path, nums, k, n):
			if k < 0:
				return -1
			if k == 0 and n == 0:
				ans.append(path[:])
				return
			for i in range(len(nums)):
				dfs(path + [nums[i]], nums[i + 1:], k - 1, n - nums[i])
		dfs([], list(range(1, 10)), k, n)
		return ans


class Solution:

	def combinationSum(self, k, target):

		def calc(s, ind, temp):
			if s == 0:
				if len(temp) == k:
					ans.append(temp[:])
					return
				return
			for i in range(ind, len(arr)):
				if i > ind and arr[i] == arr[i - 1]:
					continue
				if arr[i] > s:
					break
				temp.append(arr[i])
				calc(s - arr[i], i + 1, temp)
				temp.pop()
		ans = []
		arr = [i for i in range(1, 10)]
		arr.sort()
		calc(target, 0, [])
		return ans


class Solution:

	def combinationSum(self, k, target):
		results = []
		candidates = list(range(1, 10))

		def backtrack(start, target, combination):
			if target == 0 and len(combination) == k:
				results.append(combination)
				return
			for i in range(start, len(candidates)):
				if candidates[i] > target:
					break
				if i > start and candidates[i] == candidates[i - 1]:
					continue
				backtrack(i + 1, target - candidates[i], combination + [candidates[i]])
		backtrack(0, N, [])
		return results


class Solution:

	def solve(self, k, target, i, lst, ans):
		if len(lst) == k or i > 9:
			if target == 0 and len(lst) == k:
				ans.append(tuple(lst))
			return
		lst.append(i)
		self.solve(k, target - i, i + 1, lst, ans)
		lst.pop()
		self.solve(k, target, i + 1, lst, ans)

	def combinationSum(self, K, target):
		ans = []
		lst = []
		i = 1
		self.solve(K, target, i, lst, ans)
		return ans


class Solution:

	def combinationSum(self, K, target):
		a = list(range(1, 10))

		def recurs(i, sums, vals):
			nonlocal res
			if sums == target and len(vals) == K and (vals.copy() not in res):
				res.append(vals.copy())
				return
			if sums > target or len(vals) > K or i >= len(a):
				return
			vals.append(a[i])
			recurs(i + 1, sums + a[i], vals)
			vals.pop()
			recurs(i + 1, sums, vals)
		res = []
		recurs(0, 0, [])
		return res


class Solution:

	def combinationSum(self, K, target):
		nums = [i + 1 for i in range(9)]
		ans = []

		def dfs(pos, res, total):
			if total == target and len(res) == K:
				ans.append(res.copy())
			if total > target or pos >= len(nums) or len(res) > K:
				return
			for i in range(pos, 9):
				res.append(nums[i])
				dfs(i + 1, res, total + nums[i])
				res.pop()
		dfs(0, [], 0)
		return ans


class Solution:

	def combinationSum(self, K, target):
		ans = []
		arr = []
		numlist = [1, 2, 3, 4, 5, 6, 7, 8, 9]

		def funcall(index, sumtillnow, arr):
			if len(arr) == K:
				if sumtillnow == target:
					ans.append(arr.copy())
				return
			if index < len(numlist):
				for i in range(index, len(numlist)):
					arr.append(numlist[i])
					funcall(i + 1, sumtillnow + numlist[i], arr)
					arr.pop()
		funcall(0, 0, arr)
		return ans


class Solution:

	def solve(self, K, start, sum, ans, store):
		if K == 0 and sum == 0:
			store.append(ans)
			return
		if K <= 0:
			return
		for i in range(start, 10):
			if sum - i >= 0:
				self.solve(K - 1, i + 1, sum - i, ans + [i], store)

	def combinationSum(self, K, target):
		store = []
		self.solve(K, 1, target, [], store)
		return store


class Solution:

	def combinationSum(self, K, target):

		def find(K, target, i, temp):
			if len(temp) == K and sum(temp) == target:
				res.append(temp.copy())
			elif len(temp) < K and sum(temp) < target:
				for j in range(i + 1, 10):
					if sum(temp) + j <= target:
						temp.append(j)
						find(K, target, j, temp)
						temp.pop()
		res = []
		for i in range(1, 10):
			find(K, target, i, [i])
		return res


class Solution:

	def combinationSum(self, k, n):
		ans = []
		res = []

		def backtrack(num, res, target):
			if len(res) == k:
				if target == 0:
					ans.append(res.copy())
				return
			for i in range(num + 1, 10):
				if i <= target:
					backtrack(i, res + [i], target - i)
				else:
					return
		backtrack(0, res, n)
		return ans


class Solution:

	def combinationSum(self, K, target):
		arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

		def com(i, N, K, target, arr, count, res, s, l):
			if s == target and count == K:
				res[tuple(l)] = 1
				return
			if i == N:
				return
			if count > K:
				return
			l.append(arr[i])
			s += arr[i]
			count += 1
			com(i + 1, N, K, target, arr, count, res, s, l)
			l.pop()
			s -= arr[i]
			count -= 1
			com(i + 1, N, K, target, arr, count, res, s, l)
		count = 0
		res = {}
		com(0, 9, K, target, arr, count, res, 0, [])
		final = []
		for key in res:
			final.append(list(key))
		res.clear()
		final.sort()
		return final


class Solution:

	def combinationSum(self, K, target):

		def helper(target, k, start, path, res):
			if target == 0 and k == 0:
				res.append(path)
				return
			if target < 0 or k < 0:
				return
			for i in range(start, 10):
				helper(target - i, k - 1, i + 1, path + [i], res)
		res = []
		helper(target, K, 1, [], res)
		return res


class Solution:

	def solve(self, k, n, ans, lis, num):
		if len(lis) == k:
			if n == 0:
				ans.append(tuple(lis.copy()))
			return
		for i in range(num, 10):
			lis.append(i)
			self.solve(k, n - i, ans, lis, i + 1)
			lis.pop()

	def combinationSum(self, K, target):
		ans = []
		self.solve(K, target, ans, [], 1)
		return ans


class Solution:

	def combinationSum(self, k, target):
		arr = [i for i in range(1, 10)]
		ans = []
		dummy = []
		self.answer(k, target, arr, ans, dummy, 0, 0)
		return ans

	def answer(self, k, target, arr, ans, dummy, index, ld):
		if target == 0 and ld == k:
			ans.append(list(dummy))
			return
		elif target < 0 or index > 8 or ld > k:
			return
		else:
			for i in range(index, 9):
				dummy.append(arr[i])
				self.answer(k, target - arr[i], arr, ans, dummy, i + 1, ld + 1)
				dummy.pop()


class Solution:

	def combinationSum(self, K, target):

		def solve(idx, arr, target, K, l, ans):
			if target == 0 and len(l) == K:
				ans.append(l.copy())
				return
			for i in range(idx, len(arr)):
				if i > idx and arr[i] == arr[i - 1]:
					continue
				if arr[i] > target:
					break
				l.append(arr[i])
				solve(i + 1, arr, target - arr[i], K, l, ans)
				l.pop()
		arr = [i for i in range(1, 10)]
		ans = []
		solve(0, arr, target, K, [], ans)
		return ans


def rec(i, ans, res, target, K):
	if K == 0 and target == 0:
		ans.append(res.copy())
	if K == 0 or target < 0:
		return
	for j in range(i, 10):
		res.append(j)
		rec(j + 1, ans, res, target - j, K - 1)
		res.pop()

class Solution:

	def combinationSum(self, K, target):
		ans = []
		res = []
		rec(1, ans, res, target, K)
		return ans


class Solution:

	def combinationSum(self, K, target):
		if K > target:
			return []
		options = (1, 2, 3, 4, 5, 6, 7, 8, 9)
		res = []

		def helper(idx, sumi, temp):
			if sumi > target:
				return
			if len(temp) == K:
				if sumi == target:
					res.append(temp.copy())
				return
			for i in range(idx, len(options)):
				temp.append(options[i])
				helper(i + 1, sumi + options[i], temp)
				temp.pop()
		helper(0, 0, [])
		return res


class Solution:

	def combinationSum(self, K, target):
		ans = []
		li = []

		def helper(i, k, target, ans, li):
			if k == 0:
				if target == 0:
					ans.append(list(li))
					return
			if i > 9:
				return
			li.append(i)
			helper(i + 1, k - 1, target - i, ans, li)
			li.pop()
			helper(i + 1, k, target, ans, li)
			return
		helper(1, K, target, ans, li)
		return ans


class Solution:

	def solve(self, i, Sum, k, temp, ans):
		if Sum == 0 and k == 0:
			ans.append(temp)
			print(ans)
			return
		if k == 0 or Sum > i:
			return
		if i == 10:
			return
		if Sum - i >= 0:
			temp.append(i)
			self.solve(i + 1, Sum - i, k - 1, temp, ans)
			temp.pop()
		self.solve(i + 1, Sum, k, temo, ans)

	def combinationSum(self, K, target):

		def combi(arr, p, target, sol, k, i):
			if target == 0 and len(p) == k:
				sol.append(p)
				return
			if target < 0 or len(p) > k or i == 9:
				return
			combi(arr, p + [arr[i]], target - arr[i], sol, k, i + 1)
			combi(arr, p, target, sol, k, i + 1)
		sol = []
		k = K
		combi([i for i in range(1, 10)], [], target, sol, k, 0)
		return sol


def munny(arr, ans, res, ind, target, K, sum1, co):
	if sum1 > target:
		return
	if sum1 == target and co == K:
		res.append(ans)
		return
	if co >= K:
		return
	if ind > 8:
		return
	ans.append(arr[ind])
	munny(arr, ans.copy(), res, ind + 1, target, K, sum1 + arr[ind], co + 1)
	ans.pop()
	munny(arr, ans.copy(), res, ind + 1, target, K, sum1, co)

class Solution:

	def combinationSum(self, K, target):
		ans = []
		res = []
		arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		munny(arr, ans, res, 0, target, K, 0, 0)
		return res


class Solution:

	def combinationSum(self, k, n):
		cand = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		ds = []
		a = []
		cand.sort()
		ind = 0

		def comb(ind, arr, t, a, ds):
			if t == 0 and len(ds) == k:
				a.append(ds.copy())
				return
			if t < 0:
				return
			if len(ds) > k:
				return
			for i in range(ind, len(arr)):
				if i > ind and arr[i] == arr[i - 1]:
					continue
				if arr[i] > n:
					break
				ds.append(arr[i])
				comb(i + 1, arr, t - arr[i], a, ds)
				ds.remove(arr[i])
		comb(ind, cand, n, a, ds)
		return a


class Solution:

	def combinationSum(self, K, target):
		inp_arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		res = []

		def get_sum(inp, cursum, ans, tgt, cnt):
			if cnt < K:
				for i in range(len(inp)):
					ele = inp[i]
					if cnt + 1 == K and cursum + ele == tgt:
						res.append(ans + [ele])
					elif cursum + ele < tgt:
						if i < len(inp) - 1:
							get_sum(inp[i + 1:], cursum + ele, ans + [ele], tgt, cnt + 1)
					else:
						break
		get_sum(inp_arr, 0, [], target, 0)
		return res


class Solution:

	def combinationSum(self, K, target):

		def combi(arr, p, target, sol, k, i):
			if target == 0 and len(p) == k:
				sol.append(p)
				return
			if target < 0 or len(p) > k or i == 9:
				return
			combi(arr, p + [arr[i]], target - arr[i], sol, k, i + 1)
			combi(arr, p, target, sol, k, i + 1)
		sol = []
		k = K
		combi([i for i in range(1, 10)], [], target, sol, k, 0)
		return sol


class Solution:

	def combinationSum(self, K, target):
		setti = set([(0, ())])
		output = []
		for i in range(1, 10):
			temp = set()
			for item in setti:
				summa = i + item[0]
				items = item[1] + (i,)
				if len(items) == K and summa == target:
					output.append(items)
				elif summa < target and len(items) < K:
					temp.add((summa, items))
			setti.update(temp)
		return sorted(output)


class Solution:

	def combinationSum(self, k, n):
		res = []
		candidates = [1, 2, 3, 4, 5, 6, 7, 8, 9]

		def sol(i, c, k, candidates, target):
			if target == 0 and k == 0:
				res.append(c.copy())
				return
			if k < 0 or target < 0 or i == 9:
				return
			c.append(candidates[i])
			sol(i + 1, c, k - 1, candidates, target - candidates[i])
			c.pop()
			sol(i + 1, c, k, candidates, target)
		sol(0, [], k, candidates, n)
		return res


class Solution:

	def combinationSum(self, K, target):
		valid = []
		arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

		def ans(ind, arr, K, target, temp):
			if len(temp) == K or target == 0:
				if target == 0 and len(temp) == K:
					valid.append(temp[:])
				return
			for i in range(ind, 9):
				if target < arr[i]:
					break
				temp.append(arr[i])
				ans(i + 1, arr, K, target - arr[i], temp)
				temp.pop()
		temp = []
		ans(0, arr, K, target, temp)
		return valid


class Solution:

	def combinationSum(self, K, target):
		res = []

		def backtracking(ind, total, curr):
			if len(curr[:]) == K and total == 0:
				res.append(curr[:])
				return
			if len(curr[:]) > K or total < 0:
				return
			if ind >= 10:
				return
			for i in range(ind, 10):
				curr.append(i)
				backtracking(i + 1, total - i, curr)
				curr.pop()
		backtracking(1, target, [])
		return res


class Solution:

	def combinationSum(self, K, target):
		res = []
		arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

		def helper(ind, tar, tmp):
			if len(tmp) == K:
				if tar == 0:
					res.append(tmp[:])
				return
			if len(tmp) > K:
				return
			for i in range(ind, len(arr)):
				tmp.append(arr[i])
				helper(i + 1, tar - arr[i], tmp)
				tmp.pop()
		helper(0, target, [])
		return res


class Solution:

	def __init__(self):
		self.ans = []

	def combinationSum(self, K, target):
		self.util(range(1, 10), target, [], 0, 0)
		return [k for k in self.ans if len(k) == K]

	def util(self, A, B, elements, i, sumso):
		if i == len(A):
			return
		if sumso + A[i] > B:
			return
		elif sumso + A[i] == B:
			self.ans.append([*elements, A[i]])
		else:
			self.util(A, B, [*elements, A[i]], i + 1, sumso + A[i])
			self.util(A, B, elements, i + 1, sumso)


class Solution:

	def combinationSum(self, k, n):
		result = []

		def solve(index, sum, value):
			if len(value) == k:
				if sum == n:
					result.append(value)
					return
			for i in range(index, 9 + 1):
				if i > n:
					break
				solve(i + 1, sum + i, value + [i])
		solve(1, 0, [])
		return result


class Solution:

	def combinationSum(self, K, target):
		whole = []

		def recsum(temp, ans, i):
			whole.append(temp[:])
			if len(temp) == K and target == sum(temp):
				ans.append(temp[:])
				return
			for j in range(i, 10):
				if len(temp) < K and j not in temp and (len(temp) == 0 or temp[-1] < j):
					temp.append(j)
					recsum(temp, ans, i + 1)
					temp.pop()
				else:
					continue
			return ans
		return recsum([], [], 1)


class Solution:

	def combinationSum(self, K, target, start=1, till=[]):
		if K == 1:
			if target >= start:
				if target < 10:
					return [[*till, target]]
				else:
					return []
			else:
				return []
		ans = []
		for x in range(start, 10):
			res = self.combinationSum(K - 1, target - x, x + 1, [*till, x])
			ans += res
		return ans


class Solution:

	def combinationSum(self, K, target):
		arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		k = K
		ans = []
		sum = target
		temp = []

		def combination(arr, sum, ans, temp, index, k):
			if sum == 0 and len(temp) == k:
				ans.append(temp.copy())
				return
			if len(temp) == k:
				return
			for i in range(index, len(arr)):
				if sum - arr[index] >= 0:
					temp.append(arr[i])
					combination(arr, sum - arr[i], ans, temp, i + 1, k)
					temp.remove(arr[i])
		combination(arr, sum, ans, temp, 0, k)
		return ans


class Solution:

	def combinationSum(self, K, target):
		if target > 45:
			return []
		ans = []

		def solve(temp, i):
			if len(temp) == K and sum(temp) == target:
				ans.append(temp.copy())
				return
			for j in range(i, 10):
				temp.append(j)
				solve(temp, j + 1)
				temp.pop()
		solve([], 1)
		return ans


class Solution:

	def combinationSum(self, K, target):
		arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		res = []
		self.dfs(res, arr, K, target, [])
		return res

	def dfs(self, res, arr, k, target, path):
		if target < 0 or k < 0:
			return
		elif target == 0 and k == 0:
			res.append(path)
			return
		for i in range(len(arr)):
			self.dfs(res, arr[i + 1:], k - 1, target - arr[i], path + [arr[i]])


def bt(k, n):
	times = {i: 1 for i in range(1, 10)}
	res = []
	helper(k, n, [], times, res)
	return res

def helper(k, n, temp, times, res):
	if n == 0 and len(temp) == k:
		res.append(temp.copy())
	for num in times:
		if not temp and times[num] > 0 and (n - num >= 0) and (len(temp) <= k):
			times[num] -= 1
			temp.append(num)
			helper(k, n - num, temp, times, res)
			times[num] += 1
			temp.remove(num)
		if temp and times[num] > 0 and (n - num >= 0) and (len(temp) <= k) and (temp[-1] < num):
			times[num] -= 1
			temp.append(num)
			helper(k, n - num, temp, times, res)
			times[num] += 1
			temp.remove(num)

class Solution:

	def combinationSum(self, K, target):
		return bt(K, target)


class Solution:

	def combinationSum(self, K, target):
		res = []
		op = []
		start = 0
		self.comb(res, op, start, 1, K, target)
		return res

	def comb(self, res, op, start, i, K, target):
		if start == K and target == 0:
			res.append(op.copy())
		if target == 0:
			return
		if start == K:
			return
		if i == 10:
			return
		op.append(i)
		self.comb(res, op, start + 1, i + 1, K, target - i)
		op.pop()
		self.comb(res, op, start, i + 1, K, target)


class Solution:

	def helper(self, arr, K, target, sum1, list1, count):
		if arr == []:
			return
		if count > K:
			return
		if sum1 > target:
			return
		if sum1 == target:
			if count == K:
				self.res.append(list1)
			return
		self.helper(arr[1:], K, target, sum1 + arr[0], list1 + [arr[0]], count + 1)
		self.helper(arr[1:], K, target, sum1, list1, count)

	def combinationSum(self, K, target):
		self.res = []
		arr = [i for i in range(1, 11)]
		self.helper(arr, K, target, 0, [], 0)
		return self.res


class Solution:

	def findAllcombinationSum(self, index, candidates, target, ans, ds, k):
		if index == len(candidates):
			if target == 0 and len(ds) == k:
				ans.append(ds[:])
				return
			return
		ds.append(candidates[index])
		self.findAllcombinationSum(index + 1, candidates, target - candidates[index], ans, ds, k)
		ds.remove(candidates[index])
		self.findAllcombinationSum(index + 1, candidates, target, ans, ds, k)

	def combinationSum(self, k, target):
		candidates = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		ans = []
		self.findAllcombinationSum(0, candidates, target, ans, [], k)
		return ans


class Solution:

	def findAllcombinationSum(self, index, candidates, target, ans, ds):
		if index == len(candidates):
			if target == 0:
				ans.append(ds[:])
				return
			return
		if candidates[index] <= target and candidates[index] not in ds:
			ds.append(candidates[index])
			self.findAllcombinationSum(index, candidates, target - candidates[index], ans, ds)
			ds.remove(candidates[index])
		self.findAllcombinationSum(index + 1, candidates, target, ans, ds)

	def combinationSum(self, k, target):
		candidates = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		ans = []
		self.findAllcombinationSum(0, candidates, target, ans, [])
		mysubseq = []
		for i in ans:
			if len(i) == k:
				mysubseq.append(i)
		return mysubseq


class Solution:

	def combinationSum(self, k, n):
		output = []

		def dfs(build, num, sum_so_far):
			if len(build) == k:
				if sum_so_far == n:
					output.append(build)
				return
			for i in range(num, 9 + 1):
				if sum_so_far > n:
					break
				dfs(build + [i], i + 1, sum_so_far + i)
		dfs([], 1, 0)
		return output


class Solution:

	def combinationSum(self, k, n):
		res = []

		def dfs(index, path, tot):
			if len(path) == k and tot == 0:
				res.append(path)
			for i in range(index, 10):
				if tot - i < 0:
					break
				dfs(i + 1, path + [i], tot - i)
		dfs(1, [], n)
		return res


class Solution:

	def find(self, i, p, K, target, l, l1):
		if p == K and target == 0:
			l.append(l1.copy())
			return
		if p == K:
			return
		if target == 0:
			return
		if i == 10:
			return
		l1.append(i)
		self.find(i + 1, p + 1, K, target - i, l, l1)
		l1.pop()
		self.find(i + 1, p, K, target, l, l1)

	def combinationSum(self, K, target):
		l = []
		l1 = []
		self.find(1, 0, K, target, l, l1)
		return l


class Solution:

	def solve(self, ans, output, index, nums, K, target):
		if index == len(nums):
			if K == 0 and target == 0:
				ans.append(output)
			return
		if K == 0 and target == 0:
			ans.append(output)
			return
		self.solve(ans, output, index + 1, nums, K, target)
		self.solve(ans, output + [nums[index]], index + 1, nums, K - 1, target - nums[index])

	def combinationSum(self, K, target):
		nums = [i for i in range(1, 10)]
		ans = []
		self.solve(ans, [], 0, nums, K, target)
		ans.sort()
		return ans


from copy import deepcopy, copy

class Solution:

	def subsets(self, arr):
		if len(arr) == 0:
			subsets = [[]]
			return subsets
		if len(arr) == 1:
			subsets = [[]]
			subsets.append([arr[0]])
			return subsets
		else:
			arr_other = copy(arr)
			x = arr_other.pop()
			other_subsets = self.subsets(arr_other)
			new_subsets = copy(other_subsets)
			for other_subset in other_subsets:
				new_subset = copy(other_subset)
				new_subset.append(x)
				new_subsets.append(new_subset)
			return new_subsets

	def combinationSum(self, K, target):
		arr = list(range(1, 10))
		all_subsets = self.subsets(arr)
		results = []
		for subset in all_subsets:
			if len(subset) == K and sum(subset) == target:
				results.append(subset)
		results.sort()
		return results


class Solution:

	def combinationSum(self, K, target):
		List = []

		def recur(arr, summ, count, k, target, val):
			if summ > target or count > k:
				return
			if summ == target and count == k:
				List.append(arr[:])
				return
			if val > 9:
				return
			arr.append(val)
			recur(arr, summ + val, count + 1, k, target, val + 1)
			arr.pop()
			recur(arr, summ, count, k, target, val + 1)
		recur([], 0, 0, K, target, 1)
		return List


class Solution:

	def solve(self, prev, K, N, ans, lst=[]):
		if K == 0:
			if N == 0:
				ans.append(lst.copy())
			return
		if N < 0 or K < 0:
			return
		if prev > 9:
			return
		for i in range(prev, 10):
			lst.append(i)
			self.solve(i + 1, K - 1, N - i, ans, lst)
			lst.pop()

	def combinationSum(self, K, target):
		ans = []
		self.solve(1, K, target, ans)
		return ans


class Solution:

	def combinationSum(self, K, target):
		result = []

		def solve(pos, ds, total):
			if len(ds) == K:
				if total == target:
					result.append(ds)
				return
			for i in range(pos, 9 + 1):
				solve(i + 1, ds + [i], total + i)
		solve(1, [], 0)
		return result


class Solution:

	def combinationSum(self, K, target):
		from itertools import combinations
		x = combinations([1, 2, 3, 4, 5, 6, 7, 8, 9], K)
		y = []
		for i in x:
			if sum(i) == target:
				y.append(i)
		return y


class Solution:

	def combinationSum(self, K, target):

		def rec(ind, ans, ds, s, k, target):
			if len(ds) == k and s[0] == target:
				ans.append(ds.copy())
				return
			if ind > 9:
				return
			ds.append(ind)
			s[0] += ind
			rec(ind + 1, ans, ds, s, k, target)
			s[0] -= ind
			ds.pop()
			rec(ind + 1, ans, ds, s, k, target)
		ans = []
		ds = []
		s = [0]
		rec(1, ans, ds, s, K, target)
		return ans


class Solution:

	def combinationSum(self, K, target):

		def dfs(idx, path, cur, size):
			if cur > target or size > K:
				return
			if cur == target:
				if size == K:
					ans.append(path.copy())
				return
			for i in range(idx, 10):
				dfs(i + 1, path + [i], cur + i, size + 1)
		ans = []
		dfs(1, [], 0, 0)
		return sorted(ans)