Given two integers ‘n’ and ‘sum’, find the count of all n digit numbers whose sum of digits is ‘sum’. Leading 0’s are not counted as digits. 
Example 1:
Input: n = 2, sum = 2
Output: 2
Explaination: 
The 2 digit numbers are 11 and 20.
Example 2:
Input: n = 1, sum = 10
Output: -1
Explaination: 
We cannot get sum as 10 from a single digit.
Your Task:
You do not need to read input or print anything. Your task is to complete the function countWays() which takes the value n and sum as input parameters and returns the number of possible ways modulo 10^{9}+7. If there is no possible way then it returns -1.
Expected Time Complexity: O(n*sum)
Expected Auxiliary Space: O(n*sum)
Constraints:
1 ≤ n ≤ 10^{2}
1 ≤ sum ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def countWays(self, n, Sum):
        # code here

Solutions:
class Solution:

	def countWays(self, n, Sum):
		if Sum == 0:
			if n == 1:
				return 1
			return -1
		if n * 9 < Sum:
			return -1
		dp = {}

		def rec(d, s):
			if d == 0:
				if s == 0:
					return 1
				return 0
			if (d, s) in dp:
				return dp[d, s]
			su = 0
			for i in range(10):
				su += rec(d - 1, s - i)
			dp[d, s] = su % 1000000007
			return su % 1000000007
		sum1 = 0
		for i in range(1, 10):
			sum1 = (sum1 + rec(n - 1, Sum - i)) % 1000000007
		return sum1


class Solution:

	def countWays(self, n, Sum):
		mod = int(1000000000.0 + 7)
		dp = [[0 for i in range(Sum + 1)] for j in range(n)]
		for i in range(min(10, Sum + 1)):
			dp[0][i] = 1
		for i in range(1, n):
			for j in range(Sum + 1):
				for k in range(10):
					if k < j:
						dp[i][j] += dp[i - 1][j - k]
					if k == j and i != 1:
						dp[i][j] += dp[i - 1][j - k]
				dp[i][j] = dp[i][j] % mod
		return dp[n - 1][Sum] if dp[n - 1][Sum] != 0 else -1


M = 1000000000.0 + 7

class Solution:

	def countWays(self, n, Sum):

		def f(n, Sum, target, dp):
			if n == 0:
				if Sum == 0:
					return 1
				return 0
			ans = 0
			if dp[n][Sum] != -1:
				return dp[n][Sum]
			for i in range(9, -1, -1):
				if i <= Sum:
					if i == 0 and Sum == target:
						continue
					else:
						ans += f(n - 1, Sum - i, target, dp)
						ans %= M
			dp[n][Sum] = ans
			return dp[n][Sum]
		dp = [[-1] * (Sum + 1) for i in range(n + 1)]
		count = f(n, Sum, Sum, dp)
		if count == 0:
			return -1
		return int(count)


class Solution:

	def countWays(self, n, Sum):
		if n <= 0 or Sum <= 0:
			return -1
		if Sum > n * 9:
			return -1
		Mod = 1000000007
		dp = [[0] * (Sum + 1) for _ in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(1, Sum + 1):
				for d in range(min(10, j + 1)):
					if d == 0 and n == 1:
						continue
					dp[i][j] += dp[i - 1][j - d] % Mod
					dp[i][j] = dp[i][j] % Mod
		if dp[n][Sum] > 0:
			return dp[n][Sum]
		else:
			return -1


class Solution:

	def countWays(self, n, s):
		dp = [[0 for j in range(Sum + 1)] for i in range(n)]
		for s in range(1, min(Sum + 1, 10)):
			dp[0][s] = 1
		for i in range(1, n):
			for s in range(1, Sum + 1):
				for digit in range(min(s, 10)):
					if s > digit:
						dp[i][s] += dp[i - 1][s - digit]
		if dp[n - 1][Sum] == 0:
			return -1
		else:
			return dp[n - 1][Sum] % (10 ** 9 + 7)


MOD = int(1000000000.0 + 7)

def f(n, summ, last, dp):
	if n == 0 and summ == 0:
		return 1
	if n == 0:
		return 0
	if dp[n][summ] != -1:
		return dp[n][summ]
	ans = 0
	for i in range(10):
		if i <= summ:
			ans += f(n - 1, summ - i, 1, dp)
			ans %= MOD
	dp[n][summ] = ans
	return ans

class Solution:

	def countWays(self, n, Sum):
		dp = [[-1 for i in range(Sum + 1)] for i in range(n + 1)]
		ans = 0
		try:
			for i in range(1, 10):
				if i <= Sum:
					ans += f(n - 1, Sum - i, 1, dp)
					ans %= MOD
		except Exception as e:
			print(e)
		return -1 if ans == 0 else ans


class Solution:

	def countWays(self, n, Sum):
		mod = 10 ** 9 + 7
		dp = [[0] * max(10, Sum + 1) for _ in range(n + 1)]
		dp[0][0] = 1
		for j in range(1, 10):
			dp[1][j] = 1
		for i in range(2, n + 1):
			for j in range(1, Sum + 1):
				ans = 0
				for k in range(10):
					if j >= k:
						ans += dp[i - 1][j - k]
				dp[i][j] = ans % mod
		ans = dp[n][Sum]
		return ans if ans else -1


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def recursive_thinking(self, pos, n, curr_sum, s):
		if pos == n:
			return 1 if curr_sum == s else 0
		if curr_sum == s:
			return 1
		if (pos, curr_sum) in self.tb:
			return self.tb[pos, curr_sum]
		start = 0
		ans = 0
		if pos == 0:
			start = 1
		for i in range(start, 10):
			if curr_sum + i <= s:
				ans += self.recursive_thinking(pos + 1, n, curr_sum + i, s)
		self.tb[pos, curr_sum] = ans
		return ans

	def countWays(self, n, s):
		if s == 0:
			return 1 if n == 1 else -1
		if 9 * n < s:
			return -1
		if 9 * n == s:
			return 1
		self.tb = {}
		res = self.recursive_thinking(0, n, 0, s)
		if res == 0:
			return -1
		return res % (10 ** 9 + 7)


class Solution:

	def count(self, n, Sum, dp):
		summ = 0
		if n == 0:
			return int(Sum == 0)
		if (n, Sum) in dp:
			return dp[n, Sum]
		for i in range(0, 10):
			if Sum - i >= 0:
				summ += self.count(n - 1, Sum - i, dp)
		dp[n, Sum] = summ
		return summ

	def countWays(self, n, Sum):
		summ = 0
		dp = {}
		for i in range(1, 10):
			if Sum - i >= 0:
				summ += self.count(n - 1, Sum - i, dp)
		return -1 if summ == 0 else summ % (10 ** 9 + 7)


class Solution:

	def countWays(self, n, Sum):
		mod = int(1000000000.0) + 7
		memo = {}

		def dp(size, target):
			if target < 0:
				return 0
			if size == 0:
				return 1 if target == 0 else 0
			if (size, target) in memo:
				return memo[size, target]
			ans = 0
			for x in range(10):
				ans += dp(size - 1, target - x)
			memo[size, target] = ans % mod
			return memo[size, target]
		res = 0
		for i in range(1, 10):
			res += dp(n - 1, Sum - i)
		res %= mod
		return res if res > 0 else -1


class Solution:

	def countWays(self, n, Sum):

		def solve(i, total):
			if i == n:
				if total == Sum:
					return 1
				return 0
			if dp[i][total] != -1:
				return dp[i][total]
			nums = 0
			for j in range(10):
				if i == 0 and j == 0:
					continue
				if total + j <= Sum:
					nums += solve(i + 1, total + j)
			dp[i][total] = nums
			return nums
		dp = [[-1] * 1000 for _ in range(100)]
		k = solve(0, 0)
		if k == 0:
			return -1
		return k % (pow(10, 9) + 7)


class Solution:

	def countWays(self, n, sum):
		memo = dict()

		def helper(n, sum):
			if n == 0:
				return sum == 0
			if sum == 0:
				return 1
			if (n, sum) in memo:
				return memo[n, sum]
			ans = 0
			for i in range(10):
				if sum - i >= 0:
					ans += helper(n - 1, sum - i)
			memo[n, sum] = ans % 1000000007
			return memo[n, sum]
		res = 0
		for i in range(1, 10, 1):
			if sum - i >= 0:
				res += helper(n - 1, sum - i)
		return res % 1000000007 if res != 0 else -1


class Solution:

	def countWays(self, n, sumi):
		dp = [[0 for i in range(sumi + 1)] for j in range(n + 1)]
		if n * 9 < sumi or sumi == 0:
			return -1
		for i in range(1, 10):
			if i <= sumi:
				dp[1][i] = 1
		mod = pow(10, 9) + 7
		for i in range(1, n + 1):
			for j in range(1, sumi + 1):
				for k in range(10):
					if i == 1 and k == 0:
						continue
					if j >= k:
						dp[i][j] += dp[i - 1][j - k]
		return dp[n][sumi] % mod


class Solution:

	def f(self, n, sum, dp):
		if sum == 0:
			return 1
		if n == 1:
			if sum > 9 or sum < 0:
				return 0
			return 1
		if sum < 0:
			return 0
		ans = 0
		state = (n, sum)
		if state in dp:
			return dp[state]
		for i in range(10):
			ans += self.f(n - 1, sum - i, dp)
		dp[state] = ans % (10 ** 9 + 7)
		return dp[state]

	def countWays(self, n, Sum):
		if n == 1:
			if Sum >= 10:
				return -1
			return 1
		ans = 0
		dp = {}
		for i in range(1, 10):
			ans += self.f(n - 1, Sum - i, dp)
		if ans == 0:
			return -1
		return ans % (10 ** 9 + 7)


def count(n, s):
	global dp
	global mod
	try:
		return dp[n, s]
	except:
		pass
	if n == 0 and s == 0:
		return 1
	if n < 0 or s < 0:
		return 0
	res = 0
	if n != 1:
		for i in range(10):
			res = (res % mod + count(n - 1, s - i) % mod) % mod
	else:
		for i in range(1, 10):
			res = (res % mod + count(n - 1, s - i) % mod) % mod
	dp[n, s] = res % mod
	return res

class Solution:

	def countWays(self, n, Sum):
		global dp
		global mod
		mod = 1000000007
		dp = {}
		k = count(n, Sum)
		if k == 0:
			return -1
		return k


import sys
sys.setrecursionlimit(100000)

def solve(n, sm, dp, f):
	if sm == 0:
		return 1
	if n == 0 and sm != 0:
		return 0
	if n == 0 and sm == 0:
		return 1
	if sm < 0:
		return 0
	if dp[n][sm] != -1:
		return dp[n][sm]
	ans = 0
	if f == 0:
		for i in range(1, 10):
			ans += solve(n - 1, sm - i, dp, f + 1)
			ans %= 10 ** 9 + 7
	else:
		for i in range(0, 10):
			ans += solve(n - 1, sm - i, dp, f + 1)
			ans %= 10 ** 9 + 7
	dp[n][sm] = ans
	return dp[n][sm]

class Solution:

	def countWays(self, n, sm):
		dp = [[-1 for i in range(sm + 1)] for j in range(n + 1)]
		f = 0
		solve(n, sm, dp, f)
		return dp[n][sm] if dp[n][sm] > 0 else -1