Given two integers N and K, the task is to count the number of ways to divide N into groups of positive integers. Such that each group shall have K elements and their sum is N. Also the number of elements in the groups follows a non-decreasing order (i.e. group[i] <= group[i+1]). Find the number of such groups
Example 1:
Input:
N = 8
K = 4
Output:
5
Explanation:
There are 5 groups such that their sum is 8 
and the number of positive integers in each 
group is 4. The 5 groups are [1, 1, 1, 5], 
[1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3] and 
[2, 2, 2, 2].
Example 2:
Input: 
N = 4
K = 3
Output:
1
Explanation: 
The only possible grouping is {1, 1, 2}. Hence,
the answer is 1 in this case.
Your Task:
Complete the function countWaystoDivide() which takes the integers N and K as the input parameters, and returns the number of ways to divide the sum N into K groups.
Expected Time Complexity: O(N^{2}*K)
Expected Auxiliary Space: O(N^{2}*K)
Constraints:
1 ≤ K ≤ N ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Starter code: #User function Template for python3



class Solution:

    def countWaystoDivide(self, N, K):

        # Code here

Solutions:
import sys

class Solution:

	def countWaystoDivide(self, N, K):
		dp = [[[0 for _ in range(K + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
		for i in range(1, N + 1):
			dp[i][0][0] = 1
		for max_value in range(1, N + 1):
			for remaining_sum in range(1, N + 1):
				for remaining_groups in range(1, K + 1):
					dp[max_value][remaining_sum][remaining_groups] = dp[max_value - 1][remaining_sum][remaining_groups]
					if remaining_sum >= max_value:
						dp[max_value][remaining_sum][remaining_groups] += dp[max_value][remaining_sum - max_value][remaining_groups - 1]
		ans = 0
		for i in range(1, N + 1):
			ans += dp[i][N - i][K - 1]
		return ans


class Solution:

	def calculate(self, pos, prev, left, K, dp):
		if pos == K:
			if left == 0:
				return 1
			else:
				return 0
		if left == 0:
			return 0
		if dp[pos][left][prev] != -1:
			return dp[pos][left][prev]
		answer = 0
		for i in range(prev, left + 1):
			answer += self.calculate(pos + 1, i, left - i, K, dp)
		dp[pos][left][prev] = answer
		return answer

	def countWaystoDivide(self, N, K):
		dp = [[[-1 for j in range(N + 1)] for j in range(N + 1)] for j in range(K + 1)]
		return self.calculate(0, 1, N, K, dp)


class Solution:

	def countWaystoDivide(self, N, K):
		a = []
		for i in range(1, N + 1):
			a.append(i)
		n = N
		k = K
		dp = []
		for i in range(N + 1):
			c = []
			for j in range(N + 1):
				d = []
				for k in range(k + 1):
					d.append(-1)
				c.append(d)
			dp.append(c)

		def coin(i, su, a1):
			if su == n:
				if a1 == k:
					return 1
				else:
					return 0
			if su > n or i >= n or a1 > k:
				return 0
			if dp[i][su][a1] != -1:
				return dp[i][su][a1]
			a3 = coin(i, su + a[i], a1 + 1)
			a2 = coin(i + 1, su, a1)
			dp[i][su][a1] = a3 + a2
			return dp[i][su][a1]
		return coin(0, 0, 0)


class Solution:

	def countWaystoDivide(self, N, K):
		from functools import lru_cache

		@lru_cache(None)
		def fn(a, b, c=1):
			if b == 1:
				return 1
			ret = 0
			for i in range(c, a // 2 + 1):
				ret += fn(a - i, b - 1, i)
			return ret
		return fn(N, K)


class Solution:

	def countWaystoDivide(self, N, K):
		dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]
		for i in range(1, K + 1):
			for j in range(i, N + 1):
				if i == 1:
					dp[i][j] = 1
				elif j == i:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i - 1][j - 1] + dp[i][j - i]
		return dp[K][N]


from functools import lru_cache

class Solution:

	def countWaystoDivide(self, N, K):
		dp = {}

		@lru_cache(None)
		def helper(i, j, l):
			if j == 0 and i == 0:
				dp[0, 0] = 1
				return 1
			if i > j:
				return 0
			if i == 0:
				if j != 0:
					return 0
			x = 0
			for k in range(1, j + 1):
				if k >= l:
					x += helper(i - 1, j - k, k)
			return x
		y = helper(K, N, 0)
		return y


class Solution:

	def countWaystoDivide(self, n, k):
		dp = [[[0 for _ in range(K + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
		for i in range(1, N + 1):
			dp[i][0][0] = 1
		for max_value in range(1, N + 1):
			for remaining_sum in range(1, N + 1):
				for remaining_groups in range(1, K + 1):
					dp[max_value][remaining_sum][remaining_groups] = dp[max_value - 1][remaining_sum][remaining_groups]
					if remaining_sum >= max_value:
						dp[max_value][remaining_sum][remaining_groups] += dp[max_value][remaining_sum - max_value][remaining_groups - 1]
		ans = 0
		for i in range(1, N + 1):
			ans += dp[i][N - i][K - 1]
		return ans


class Solution:

	def countWaystoDivide(self, n, k):
		memo = {}

		def helper(i, n, k):
			if (i, n, k) in memo:
				return memo[i, n, k]
			if n == 0 and k != 0 or (n != 0 and k == 0):
				return 0
			if n == 0 and k == 0:
				return 1
			if n < 0 or i > n:
				return 0
			inc = 0
			exc = 0
			inc = helper(i, n - i, k - 1)
			exc = helper(i + 1, n, k)
			memo[i, n, k] = inc + exc
			return inc + exc
		return helper(1, n, k)


class Solution:

	def countWaystoDivide(self, N, K):

		def solve(sum_left, count, prev):
			if count == 0:
				if sum_left == 0:
					return 1
				else:
					return 0
			if sum_left == 0 and count != 0:
				return 0
			if dp[sum_left][count][prev] != -1:
				return dp[sum_left][count][prev]
			ways = 0
			for i in range(prev, sum_left + 1):
				ways += solve(sum_left - i, count - 1, i)
			dp[sum_left][count][prev] = ways
			return dp[sum_left][count][prev]
		dp = [[[-1 for i in range(0, N + 1)] for j in range(K + 1)] for k in range(N + 1)]
		return solve(N, K, 1)


class Solution:

	def countWaystoDivide(self, N, K):
		if N == K or K == 1:
			return 1
		elif N < K:
			return 0
		else:
			return self.countWaystoDivide(N - 1, K - 1) + self.countWaystoDivide(N - K, K)


class Solution:

	def countWaystoDivide(self, N, K):
		dp = [[[-1 for i in range(K + 1)] for j in range(N + 1)] for j in range(N + 1)]

		def recursive(N, K, Sum=N):
			nonlocal dp
			if Sum == 0:
				if K == 0:
					return 1
				else:
					return 0
			if K == 0 or N == 0:
				return 0
			if dp[N][Sum][K] != -1:
				return dp[N][Sum][K]
			dp[N][Sum][K] = recursive(N - 1, K, Sum)
			if N <= Sum:
				dp[N][Sum][K] += recursive(N, K - 1, Sum - N)
			return dp[N][Sum][K]
		return recursive(N, K)


class Solution:

	def countWaystoDivide(self, N, K):
		memo = [[[-1 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(K)]

		def dfs(index: int=0, last_used: int=1, left: int=N):
			if index == K - 1:
				return 1 if left >= last_used else 0
			if left <= 0:
				return 0
			if memo[index][left][last_used] > -1:
				return memo[index][left][last_used]
			res = []
			for i in range(last_used, left):
				if left >= max(0, i * (K - (index + 1))):
					res.append(dfs(index + 1, i, left - i))
			memo[index][left][last_used] = sum(res)
			return memo[index][left][last_used]
		return dfs(0, 1, N)


class Solution:

	def countWaystoDivide(self, N, K):
		if N < K:
			return 0
		T = [[0] * (K + 1) for i in range(N + 1)]
		for i in range(1, N + 1):
			T[i][1] = 1
		T[0][0] = 1
		for i in range(1, N + 1):
			for j in range(2, K + 1):
				if i >= j:
					T[i][j] = T[i - 1][j - 1] + T[i - j][j]
				else:
					T[i][j] = T[i - 1][j - 1]
		return T[N][K]


class Solution:

	def countWaystoDivide(self, N, K):
		if N < K:
			return 0
		if K == 1:
			return 1
		return self.countWaystoDivide(N - K, K) + self.countWaystoDivide(N - 1, K - 1)


class Solution:

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

	def solve(self, sum_left, count, prev):
		if count == 0:
			if sum_left == 0:
				return 1
			return 0
		if sum_left == 0:
			return 0
		if self.dp[sum_left][prev][count] != -1:
			return self.dp[sum_left][prev][count]
		ways = 0
		for i in range(prev, sum_left + 1):
			ways += self.solve(sum_left - i, count - 1, i)
		self.dp[sum_left][prev][count] = ways
		return ways

	def countWaystoDivide(self, N, K):
		self.dp = [[[-1 for _ in range(K + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
		return self.solve(N, K, 1)


class Solution:

	def countWaystoDivide(self, n, k):
		dp = []
		for i in range(n + 1):
			l1 = []
			for j in range(n + 1):
				l2 = []
				for z in range(k + 1):
					l2.append(-1)
				l1.append(l2)
			dp.append(l1)
		return solve(n, k, 1, dp)

def solve(s, c, p, dp):
	if c == 0:
		if s == 0:
			return 1
		else:
			return 0
	if s == 0:
		return 0
	ans = 0
	if dp[s][p][c] != -1:
		return dp[s][p][c]
	for i in range(p, s + 1):
		ans += solve(s - i, c - 1, i, dp)
	dp[s][p][c] = ans
	return ans


class Solution:

	def countWaystoDivide(self, N, K):
		dp = [[0 for j in range(K + 1)] for i in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			dp[i][0] = 0
			dp[i][1] = 1
		for j in range(2, K + 1):
			for i in range(j, N + 1):
				dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]
		return dp[N][K]


class Solution:

	def countWaystoDivide(self, n, k):
		if k > n:
			return 0

		def func(dp, ind, tar, k, n):
			if ind > n:
				return 0
			if ind == n and tar == 0 and (k == 0):
				return 1
			if tar < 0 or k < 0:
				return 0
			if dp[ind][tar][k] != -1:
				return dp[ind][tar][k]
			take = 0
			if tar >= ind:
				take = func(dp, ind, tar - ind, k - 1, n)
			nottake = func(dp, ind + 1, tar, k, n)
			dp[ind][tar][k] = take + nottake
			return dp[ind][tar][k]
		dp = [[[-1 for i in range(n + 1)] for j in range(n + 1)] for k in range(n + 1)]
		return func(dp, 1, n, k, n)


class Solution:

	def countWaystoDivide(self, n, k):
		from functools import lru_cache

		@lru_cache(None)
		def count(n, k, mv):
			if k > n or k < 0 or n < 0:
				return 0
			if k == 0 and n == 0:
				return 1
			ans = 0
			for v in range(mv, n - (k - 1) + 1):
				ans += count(n - v, k - 1, v)
			return ans
		return count(N, K, 1)


class Solution:

	def countWaystoDivide(self, n: int, k: int) -> int:
		if n < k:
			return 0
		dp = [[0 for j in range(k + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][1] = 1
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(2, k + 1):
				if i >= j:
					dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]
				else:
					dp[i][j] = dp[i - 1][j - 1]
		return dp[n][k]


class Solution:

	def countWaystoDivide(self, N, K):
		y = [i for i in range(1, N + 1)]
		jk = [[[-1] * (K + 1) for i in range(N + 1)] for j in range(N + 1)]

		def coin(i, ko, lp):
			if ko == N:
				if lp == K:
					return 1
				else:
					return 0
			if ko > N or i >= N or lp > K:
				return 0
			if jk[i][ko][lp] != -1:
				return jk[i][ko][lp]
			a3 = coin(i, ko + y[i], lp + 1)
			a2 = coin(i + 1, ko, lp)
			jk[i][ko][lp] = a3 + a2
			return jk[i][ko][lp]
		return coin(0, 0, 0)


class Solution:

	def __init__(self):
		self.cache = {}

	def dp(self, nxt, summ, n):
		if summ == 0 and n == 0:
			return 1
		if summ <= 0 or n == 0:
			return 0
		if (nxt, summ, n) in self.cache:
			return self.cache[nxt, summ, n]
		ans = 0
		for i in range(1, nxt + 1):
			ans += self.dp(i, summ - i, n - 1)
		self.cache[nxt, summ, n] = ans
		return ans

	def countWaystoDivide(self, N, K):
		ans = 0
		for i in range(1, N + 1):
			ans += self.dp(i, N - i, K - 1)
		return ans


class Solution:

	def countWaystoDivide(self, N, K):
		memo = {}

		def dp(i, remain, total, memo):
			if total > N:
				return 0
			if remain == 0:
				if total == N:
					return 1
				return 0
			if i > N:
				return 0
			if (i, remain, total) in memo:
				return memo[i, remain, total]
			memo[i, remain, total] = dp(i, remain - 1, total + i, memo) + dp(i + 1, remain, total, memo)
			return memo[i, remain, total]
		return dp(1, K, 0, memo)


class Solution:

	def countWaystoDivide(self, N, K):
		if K > N:
			return 0

		def func(dp, ind, tar, K, N):
			if ind > N:
				return 0
			if ind == N and tar == 0 and (K == 0):
				return 1
			if tar < 0 or K < 0:
				return 0
			if dp[ind][tar][K] != -1:
				return dp[ind][tar][K]
			take = 0
			if tar >= ind:
				take = func(dp, ind, tar - ind, K - 1, N)
			nottake = func(dp, ind + 1, tar, K, N)
			dp[ind][tar][K] = take + nottake
			return dp[ind][tar][K]
		dp = [[[-1 for i in range(N + 1)] for j in range(N + 1)] for K in range(N + 1)]
		return func(dp, 1, N, K, N)


class Solution:

	def s(self, n, k, p, dp):
		if k == 0:
			if n == 0:
				return 1
			return 0
		if n <= 0:
			return 0
		if dp[n][k][p] != -1:
			return dp[n][k][p]
		w = 0
		for i in range(p, n + 1):
			w = w + self.s(n - i, k - 1, i, dp)
		dp[n][k][p] = w
		return w

	def countWaystoDivide(self, N, K):
		dp = []
		for i in range(N + 2):
			t2 = []
			for j in range(K + 2):
				t1 = []
				for k in range(N + 2):
					t1.append(-1)
				t2.append(t1)
			dp.append(t2)
		return self.s(N, K, 1, dp)


class Solution:

	def countWaystoDivide(self, N, K):
		a = [i for i in range(1, N + 1)]
		dp = [[[-1] * (K + 1) for i in range(N + 1)] for j in range(N + 1)]

		def coin(i, su, a1):
			if su == N:
				if a1 == K:
					return 1
				else:
					return 0
			if su > N or i >= N or a1 > K:
				return 0
			if dp[i][su][a1] != -1:
				return dp[i][su][a1]
			a3 = coin(i, su + a[i], a1 + 1)
			a2 = coin(i + 1, su, a1)
			dp[i][su][a1] = a3 + a2
			return dp[i][su][a1]
		return coin(0, 0, 0)


class Solution:

	def countWaystoDivide(self, N, K):
		if N < K:
			return 0

		def solve(P, N, K):
			if N < K * P:
				return 0
			if K == 1 and N > 0 or P * K == N:
				return 1
			i = P
			s = 0
			while i * K <= N:
				s += solve(i, N - i, K - 1)
				i += 1
			return s
		return solve(1, N, K)


import sys
sys.setrecursionlimit(1500)

class Solution:

	def countWaystoDivide(self, N, K):
		cache = [[[None] * (N + 1) for i in range(N + 1)] for k in range(K + 1)]

		def helper(k, _sum, i):
			if _sum > N:
				return 0
			if k == 0:
				if _sum == N:
					cache[k][_sum][i] = 1
					return 1
				else:
					cache[k][_sum][i] = 0
					return 0
			if i > N:
				return 0
			if cache[k][_sum][i] is None:
				cache[k][_sum][i] = helper(k - 1, _sum + i, i) + helper(k, _sum, i + 1)
			return cache[k][_sum][i]
		return helper(K, 0, 1)


class Solution:

	def countWaystoDivide(self, N, K):
		a = []
		for i in range(1, N + 1):
			a.append(i)
		n = N
		k = K
		dp = []
		for i in range(N + 1):
			c = []
			for j in range(N + 1):
				d = []
				for k in range(k + 1):
					d.append(-1)
				c.append(d)
			dp.append(c)

		def util(i, su, b):
			if su == n:
				if b == k:
					return 1
				else:
					return 0
			if su > n or i >= n or b > k:
				return 0
			if dp[i][su][b] != -1:
				return dp[i][su][b]
			x = util(i, su + a[i], b + 1)
			y = util(i + 1, su, b)
			dp[i][su][b] = x + y
			return dp[i][su][b]
		return util(0, 0, 0)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def countWaystoDivide(self, n, s):

		def csum(ind, t, co):
			if ind > n:
				return 0
			if ind == n and t == 0 and (co == 0):
				return 1
			if t < 0 or co < 0:
				return 0
			if dp[ind][t][co] != -1:
				return dp[ind][t][co]
			p = 0
			if ind <= t:
				p = csum(ind, t - ind, co - 1)
			np = csum(ind + 1, t, co)
			dp[ind][t][co] = p + np
			return p + np
		dp = [[[-1] * (s + 1) for i in range(n + 1)] for j in range(n + 1)]
		return csum(1, n, s)


class Solution:

	def countWaystoDivide(self, N, K):
		arr = []
		for i in range(1, N + 1):
			arr.append(i)
		(n, k) = (N, K)
		dp = []
		for i in range(N + 1):
			t1 = []
			for j in range(N + 1):
				t2 = []
				for k in range(k + 1):
					t2.append(-1)
				t1.append(t2)
			dp.append(t1)

		def fun(a, b, c):
			if b == n:
				if c == k:
					return 1
				else:
					return 0
			if b > n or a >= n or c > k:
				return 0
			if dp[a][b][c] != -1:
				return dp[a][b][c]
			p = fun(a, b + arr[a], c + 1)
			q = fun(a + 1, b, c)
			dp[a][b][c] = p + q
			return dp[a][b][c]
		return fun(0, 0, 0)


class Solution:

	def countWaystoDivide(self, N, K):
		if K > N:
			return 0

		def func(dp, ind, tar, K, N):
			if ind > N:
				return 0
			if ind == N and tar == 0 and (K == 0):
				return 1
			if tar < 0 or K < 0:
				return 0
			if dp[ind][tar][K] != -1:
				return dp[ind][tar][K]
			flag = 0
			if tar >= ind:
				flag = func(dp, ind, tar - ind, K - 1, N)
			notflag = func(dp, ind + 1, tar, K, N)
			dp[ind][tar][K] = flag + notflag
			return dp[ind][tar][K]
		dp = [[[-1 for i in range(N + 1)] for j in range(N + 1)] for K in range(N + 1)]
		return func(dp, 1, N, K, N)


from functools import lru_cache

class Solution:

	def countWaystoDivide(self, N, K):

		@lru_cache(None)
		def helper(k, n, prev):
			if k == 0:
				return 1 if n == 0 else 0
			res = 0
			for i in range(1, min(n, prev) + 1):
				res += helper(k - 1, n - i, i)
			return res
		return helper(K, N, N)


class Solution:

	def countWaystoDivide(self, N, K):
		max_val = N - (K - 1)
		mat = [[[0 for _ in range(max_val + 1)] for _ in range(N + 1)] for _ in range(K + 1)]
		return self.ways_to_divide(N, K, max_val, mat)

	def ways_to_divide(self, N, K, max_val, mat):
		if mat[K][N][max_val]:
			return mat[K][N][max_val]
		if K == 1:
			return 1
		count = 0
		max_val = min(N - (K - 1), max_val)
		min_val = N // K + (N % K > 0)
		for val in range(min_val, max_val + 1):
			count += self.ways_to_divide(N - val, K - 1, val, mat)
		mat[K][N][max_val] = count
		return count