Different ways to sum n using numbers greater than or equal to m

Given two natural numbers n and m. The task is to find the number of ways in which the numbers that are greater than or equal to m can be added to get the sum n.

Examples: 

Input: n = 3, m = 1
Output: 3
Explanation: Three different ways to get sum n such that each term is greater than or equal to m are 1 + 1 + 1, 1 + 2 and 3

Input: n = 2, m = 1
Output: 2
Explanation: Two different ways to get sum n such that each term is greater than or equal to m are 1 + 1 and 2

Using Recursion - O(2^n) Time and O(n) Space

The idea is to find the number of ways to reach n by trying each value of m from m to n. Starting from the target sum n, for each m, we can either include it or exclude it. If we include it, we subtract its value from sum and recursively try to make the remaining amount with the same value. If we exclude it, we move to (m+1).

Mathematically the recurrence relation will look like the following:

• count(m, n) = count(m, n-m) + count(m+1, n)

Base cases:

• count(m, n) = 0, if n < 0 or m > n.
• count(m, n) = 1, if n == 0.

// C++ program to find ways  // to make sum n, using values // greater than equal to m using recursion #include <bits/stdc++.h> using namespace std; int countRecur(int m, int n) {    // base case   if (n==0) return 1;  if (m>n || n<0) return 0;    // include current m   int take = countRecur(m, n-m);    // skip current m   int noTake = countRecur(m+1, n);    return take+noTake; } int count(int m, int n) {  return countRecur(m, n); } int main() {  int n = 3, m = 1;  cout<<count(m,n);  return 0; } 

// Java program to find ways  // to make sum n, using values // greater than equal to m using recursion class GfG {  // Function to recursively count ways  static int countRecur(int m, int n) {    // base case   if (n == 0) return 1;  if (m > n || n < 0) return 0;    // include current m   int take = countRecur(m, n - m);    // skip current m   int noTake = countRecur(m + 1, n);    return take + noTake;  }  static int count(int m, int n) {  return countRecur(m, n);  }  public static void main(String[] args) {  int n = 3, m = 1;  System.out.println(count(m, n));  } } 

# Python program to find ways  # to make sum n, using values # greater than equal to m using recursion def countRecur(m, n): # base case  if n == 0: return 1 if m > n or n < 0: return 0 # include current m  take = countRecur(m, n - m) # skip current m  noTake = countRecur(m + 1, n) return take + noTake def count(m, n): return countRecur(m, n) if __name__ == "__main__": n = 3 m = 1 print(count(m, n)) 

// C# program to find ways  // to make sum n, using values // greater than equal to m using recursion using System; class GfG {  // Function to recursively count ways  static int countRecur(int m, int n) {    // base case   if (n == 0) return 1;  if (m > n || n < 0) return 0;    // include current m   int take = countRecur(m, n - m);    // skip current m   int noTake = countRecur(m + 1, n);    return take + noTake;  }  static int count(int m, int n) {  return countRecur(m, n);  }  static void Main(string[] args) {  int n = 3, m = 1;  Console.WriteLine(count(m, n));  } } 

// JavaScript program to find ways  // to make sum n, using values // greater than equal to m using recursion // Function to recursively count ways function countRecur(m, n) {    // base case   if (n === 0) return 1;  if (m > n || n < 0) return 0;    // include current m   const take = countRecur(m, n - m);    // skip current m   const noTake = countRecur(m + 1, n);    return take + noTake; } function count(m, n) {  return countRecur(m, n); } const n = 3, m = 1; console.log(count(m, n)); 

3

Using Top-Down DP (Memoization) - O(n^2) Time and O(n^2) Space

If we notice carefully, we can observe that the above recursive solution holds the following two properties of Dynamic Programming:

1. Optimal Substructure: Number of ways to make sum n at value m, i.e., count(m, n), depends on the optimal solutions of the subproblems count(m, n-m) and count(m+1, n). By combining these optimal substructures, we can efficiently calculate the number of ways to make target sum n at value m.

2. Overlapping Subproblems: While applying a recursive approach in this problem, we notice that certain subproblems are computed multiple times.

• There are only are two parameters: m and n that changes in the recursive solution. The value of m will be in range [m, n] So we create a 2D matrix of size (n+1)*(n+1) for memoization.
• We initialize this matrix as -1 to indicate nothing is computed initially.
• Now we modify our recursive solution to first check if the value is -1, then only make recursive calls. This way, we avoid re-computations of the same subproblems.

// C++ program to find ways  // to make sum n, using values // greater than equal to m using memoization #include <bits/stdc++.h> using namespace std; int countRecur(int m, int n, vector<vector<int>> &memo) {    // base case   if (n==0) return 1;  if (m>n || n<0) return 0;    // If value if memoized  if (memo[m][n]!=-1) return memo[m][n];    // include current m   int take = countRecur(m, n-m, memo);    // skip current m   int noTake = countRecur(m+1, n, memo);    return memo[m][n] = take+noTake; } int count(int m, int n) {  vector<vector<int>> memo(n+1, vector<int>(n+1, -1));  return countRecur(m, n, memo); } int main() {  int n = 3, m = 1;  cout<<count(m,n);  return 0; } 

// Java program to find ways  // to make sum n, using values // greater than equal to m using memoization class GfG {  // Function to recursively count ways  static int countRecur(int m, int n, int[][] memo) {    // base case   if (n == 0) return 1;  if (m > n || n < 0) return 0;    // If value is memoized  if (memo[m][n] != -1) return memo[m][n];    // include current m   int take = countRecur(m, n - m, memo);    // skip current m   int noTake = countRecur(m + 1, n, memo);    return memo[m][n] = take + noTake;  }  static int count(int m, int n) {  int[][] memo = new int[n + 1][n + 1];  for (int[] row : memo) {  java.util.Arrays.fill(row, -1);  }  return countRecur(m, n, memo);  }  public static void main(String[] args) {  int n = 3, m = 1;  System.out.println(count(m, n));  } } 

# Python program to find ways  # to make sum n, using values # greater than equal to m using memoization def countRecur(m, n, memo): # base case  if n == 0: return 1 if m > n or n < 0: return 0 # If value is memoized if memo[m][n] != -1: return memo[m][n] # include current m  take = countRecur(m, n - m, memo) # skip current m  noTake = countRecur(m + 1, n, memo) memo[m][n] = take + noTake return memo[m][n] def count(m, n): memo = [[-1 for _ in range(n + 1)] for _ in range(n + 1)] return countRecur(m, n, memo) if __name__ == "__main__": n = 3 m = 1 print(count(m, n)) 

// C# program to find ways  // to make sum n, using values // greater than equal to m using memoization using System; class GfG {  // Function to recursively count ways  static int countRecur(int m, int n, int[,] memo) {    // base case   if (n == 0) return 1;  if (m > n || n < 0) return 0;    // If value is memoized  if (memo[m, n] != -1) return memo[m, n];    // include current m   int take = countRecur(m, n - m, memo);    // skip current m   int noTake = countRecur(m + 1, n, memo);    return memo[m, n] = take + noTake;  }  static int count(int m, int n) {  int[,] memo = new int[n + 1, n + 1];  for (int i = 0; i <= n; i++) {  for (int j = 0; j <= n; j++) {  memo[i, j] = -1;  }  }  return countRecur(m, n, memo);  }  static void Main(string[] args) {  int n = 3, m = 1;  Console.WriteLine(count(m, n));  } } 

// JavaScript program to find ways  // to make sum n, using values // greater than equal to m using memoization // Function to recursively count ways function countRecur(m, n, memo) {    // base case   if (n === 0) return 1;  if (m > n || n < 0) return 0;    // If value is memoized  if (memo[m][n] !== -1) return memo[m][n];    // include current m   const take = countRecur(m, n - m, memo);    // skip current m   const noTake = countRecur(m + 1, n, memo);    memo[m][n] = take + noTake;  return memo[m][n]; } function count(m, n) {  const memo = Array.from({ length: n + 1 }, () => Array(n + 1).fill(-1));  return countRecur(m, n, memo); } const n = 3, m = 1; console.log(count(m, n)); 

3

Using Bottom-Up DP (Tabulation) - O(n^2) Time and O(n^2) Space

The idea is to fill the DP table based on previous values. For each value m, we either include it or exclude it to compute the number of ways needed for each sum n. The table is filled in an iterative manner from i = n to i = m and for each sum from 1 to n.

The dynamic programming relation is as follows: 

• if (sum-i) is greater than equal to 0, then dp[i][sum] = dp[i][sum-i] + dp[i+1][sum]
• else dp[i][sum] = dp[i+1][sum].

// C++ program to find ways  // to make sum n, using values // greater than equal to m using tabulation #include <bits/stdc++.h> using namespace std; int count(int m, int n) {  if (m>n) return 0;    vector<vector<int>> dp(n+2, vector<int>(n+1));    // set dp[i][0] = 1   for (int i=0; i<n+2; i++) {  dp[i][0] = 1;  }    for (int i=n; i>=m; i--) {  for (int sum=1; sum<=n; sum++) {  if (sum-i>=0) {  dp[i][sum] = dp[i][sum-i] + dp[i+1][sum];  }  else {  dp[i][sum] = dp[i+1][sum];  }  }  }    return dp[m][n]; } int main() {  int n = 3, m = 1;  cout<<count(m,n);  return 0; } 

// Java program to find ways  // to make sum n, using values // greater than equal to m using tabulation class GfG {  static int count(int m, int n) {  if (m > n) return 0;  int[][] dp = new int[n + 2][n + 1];  // set dp[i][0] = 1   for (int i = 0; i < n + 2; i++) {  dp[i][0] = 1;  }  for (int i = n; i >= m; i--) {  for (int sum = 1; sum <= n; sum++) {  if (sum - i >= 0) {  dp[i][sum] = dp[i][sum - i] + dp[i + 1][sum];  } else {  dp[i][sum] = dp[i + 1][sum];  }  }  }  return dp[m][n];  }  public static void main(String[] args) {  int n = 3, m = 1;  System.out.println(count(m, n));  } } 

# Python program to find ways  # to make sum n, using values # greater than equal to m using tabulation def count(m, n): if m > n: return 0 dp = [[0] * (n + 1) for _ in range(n + 2)] # set dp[i][0] = 1  for i in range(n + 2): dp[i][0] = 1 for i in range(n, m - 1, -1): for sum in range(1, n + 1): if sum - i >= 0: dp[i][sum] = dp[i][sum - i] + dp[i + 1][sum] else: dp[i][sum] = dp[i + 1][sum] return dp[m][n] if __name__ == "__main__": n = 3 m = 1 print(count(m, n)) 

// C# program to find ways  // to make sum n, using values // greater than equal to m using tabulation using System; class GfG {  static int count(int m, int n) {  if (m > n) return 0;  int[,] dp = new int[n + 2, n + 1];  // set dp[i, 0] = 1   for (int i = 0; i < n + 2; i++) {  dp[i, 0] = 1;  }  for (int i = n; i >= m; i--) {  for (int sum = 1; sum <= n; sum++) {  if (sum - i >= 0) {  dp[i, sum] = dp[i, sum - i] + dp[i + 1, sum];  } else {  dp[i, sum] = dp[i + 1, sum];  }  }  }  return dp[m, n];  }  static void Main(string[] args) {  int n = 3, m = 1;  Console.WriteLine(count(m, n));  } } 

// JavaScript program to find ways  // to make sum n, using values // greater than equal to m using tabulation function count(m, n) {  if (m > n) return 0;  const dp = Array.from({ length: n + 2 },   () => Array(n + 1).fill(0));  // set dp[i][0] = 1   for (let i = 0; i < n + 2; i++) {  dp[i][0] = 1;  }  for (let i = n; i >= m; i--) {  for (let sum = 1; sum <= n; sum++) {  if (sum - i >= 0) {  dp[i][sum] =   dp[i][sum - i] + dp[i + 1][sum];  } else {  dp[i][sum] = dp[i + 1][sum];  }  }  }  return dp[m][n]; } const n = 3, m = 1; console.log(count(m, n)); 

3

Using Space Optimized DP - O(n^2) Time and O(n) Space

In previous approach of dynamic programming we have derive the relation between states as given below:

• if (sum-i) is greater than 0, then dp[i][sum] = dp[i][sum-i] + dp[i+1][sum]
• else dp[i][sum] = dp[i+1][sum].

If we observe that for calculating current dp[i][sum] state we only need previous row dp[i-1][sum] or current row dp[i][sum-i]. There is no need to store all the previous states just one previous state is used to compute result.

// C++ program to find ways // to make sum n, using values // greater than equal to m using Space Optimized DP #include <bits/stdc++.h> using namespace std; int count(int m, int n) {  if (m > n)  return 0;  vector<int> dp(n + 1, 0);  // set dp[0] = 1  dp[0] = 1;  for (int i = n; i >= m; i--) {  for (int sum = 1; sum <= n; sum++) {  if (sum - i >= 0) {  dp[sum] = dp[sum - i] + dp[sum];  }  else {  dp[sum] = dp[sum];  }  }  }  return dp[n]; } int main() {    int n = 3, m = 1;  cout << count(m, n);  return 0; } 

// Java program to find ways  // to make sum n, using values // greater than equal to m using Space Optimized DP class GfG {  static int count(int m, int n) {  if (m > n) return 0;  int[] dp = new int[n + 1];  // set dp[0] = 1   dp[0] = 1;  for (int i = n; i >= m; i--) {  for (int sum = 1; sum <= n; sum++) {  if (sum - i >= 0) {  dp[sum] = dp[sum - i] + dp[sum];  } else {  dp[sum] = dp[sum];  }  }  }  return dp[n];  }  public static void main(String[] args) {  int n = 3, m = 1;  System.out.println(count(m, n));  } } 

# Python program to find ways  # to make sum n, using values # greater than equal to m using Space Optimized DP def count(m, n): if m > n: return 0 dp = [0] * (n + 1) # set dp[0] = 1  dp[0] = 1 for i in range(n, m - 1, -1): for sum in range(1, n + 1): if sum - i >= 0: dp[sum] = dp[sum - i] + dp[sum] else: dp[sum] = dp[sum] return dp[n] if __name__ == "__main__": n = 3 m = 1 print(count(m, n)) 

// C# program to find ways  // to make sum n, using values // greater than equal to m using Space Optimized DP using System; class GfG {  static int count(int m, int n) {  if (m > n) return 0;  int[] dp = new int[n + 1];  // set dp[0] = 1   dp[0] = 1;  for (int i = n; i >= m; i--) {  for (int sum = 1; sum <= n; sum++) {  if (sum - i >= 0) {  dp[sum] = dp[sum - i] + dp[sum];  } else {  dp[sum] = dp[sum];  }  }  }  return dp[n];  }  static void Main(string[] args) {  int n = 3, m = 1;  Console.WriteLine(count(m, n));  } } 

// JavaScript program to find ways  // to make sum n, using values // greater than equal to m using Space Optimized DP function count(m, n) {  if (m > n) return 0;  const dp = new Array(n + 1).fill(0);  // set dp[0] = 1   dp[0] = 1;  for (let i = n; i >= m; i--) {  for (let sum = 1; sum <= n; sum++) {  if (sum - i >= 0) {  dp[sum] = dp[sum - i] + dp[sum];  } else {  dp[sum] = dp[sum];  }  }  }  return dp[n]; } const n = 3, m = 1; console.log(count(m, n)); 

3