# algorithms – Count number of ways to arrive at sum N given set of numbers >= M Problem: Count number of ways to arrive at sum N given set of numbers >= M

Inputs: N = 3, M = 1 | Ways: 1 + 1 + 1, 1 + 2, 3 | Output: 3

I could see an ideal solution would be DP (Dynamic Programming) instead of combinations of every pair of numbers.

• However I find it hard how to start and proceed with the calculations.
• Looked for existing implementations, can’t find a clear source. Need help.
``````import numpy as np

# Return number of ways to which numbers
# that are greater than given number can
# be added to get sum.

def numberofways(n, m) :

dp = np.zeros((n + 2, n + 2))

dp(0)(n + 1) = 1

# Filling the table. k is for numbers
# greater than or equal that are allowed.
for k in range(n, m - 1, -1):

# i is for sum
for i in range(n + 1):

# initializing dp(i)(k) to number
# ways to get sum using numbers
# greater than or equal k+1
dp(i)(k) = dp(i)(k + 1)

# if i > k
if (i - k >= 0):
dp(i)(k) = (dp(i)(k) + dp(i - k)(k))

return dp(n)(m)

# Driver Code
if __name__ == "__main__":
n, m = (int(i) for i in input().split())
print(numberofways(n, m))

``````

References:
https://www.geeksforgeeks.org/different-ways-sum-n-using-numbers-greater-equal-m/ 