Given two numbers 
and 
. The task is to find the number of ways in which a can be represented by a set 
such that 
and the summation of these numbers is equal to a. Also 
(maximum size of the set cannot exceed m).
Examples:
Input : a = 4, m = 4
Output : 2 –> ({4}, {3, 1})
Note: {2, 2} is not a valid set as values are not in decreasing orderInput : a = 7, m = 5
Output : 5 –> ({7}, {6, 1}, {5, 2}, {4, 3}, {4, 2, 1})
Approach: This problem can be solved by Divide and Conquer using a recursive approach which follows the following conditions:
- If a is equal to zero, one solution has been found.
- If a > 0 and m == 0, this set violates the condition as no further values can be added in the set.
- If calculation has already been done for given values of a, m and prev (last value included in the current set), return that value.
- Start a loop from i = a till 0 and if i < prev, count the number of solutions if we include i in the current set and return it.
Below is the implementation of the above approach:
C++
// C++ code to calculate the number of ways// in which a given number can be represented// as set of finite numbers#include <bits/stdc++.h> #include <unordered_map> using namespace std;// Initialize dictionary which is used// to check if given solution is already// visited or not to avoid// calculating it againunordered_map<string, bool> visited;// Initialize dictionary which is used to// store the number of ways in which solution// can be obtained for given valuesunordered_map<string, int> numWays;// This function returns the total number// of sets which satisfy given criteria// a --> number to be divided into sets// m --> maximum possible size of the set// x --> previously selected valueint countNumOfWays(int a, int m, int prev) { // number is divided properly and // hence solution is obtained if (a == 0) return 1; // Solution can't be obtained if (a > 0 && m == 0) return 0; // Return the solution if it has // already been calculated string key = to_string(a) + "|" + to_string(m) + "|" + to_string(prev); if (visited.find(key) != visited.end()) return numWays[key]; visited[key] = true; for (int i = a; i >= 0; i--) { // Continue only if current value is // smaller compared to previous value if (i < prev) numWays[key] += countNumOfWays(a - i, m - 1, i); } return numWays[key]; } // Values of 'a' and 'm' for which // solution is to be found int a = 7, m = 5, MAX_CONST = 10e5; // Driver code int main() { cout << countNumOfWays(a, m, MAX_CONST) << endl; return 0; } |
Python3
# Python3 code to calculate the number of ways# in which a given number can be represented# as set of finite numbers# Import function to initialize the dictionaryfrom collections import defaultdict# Initialize dictionary which is used# to check if given solution is already# visited or not to avoid# calculating it againvisited = defaultdict(lambda: False)# Initialize dictionary which is used to# store the number of ways in which solution# can be obtained for given valuesnumWays = defaultdict(lambda: 0)# This function returns the total number# of sets which satisfy given criteria# a --> number to be divided into sets# m --> maximum possible size of the set# x --> previously selected valuedef countNumOfWays(a, m, prev): # number is divided properly and # hence solution is obtained if a == 0: return 1 # Solution can't be obtained elif a > 0 and m == 0: return 0 # Return the solution if it has # already been calculated elif visited[(a, m, prev)] == True: return numWays[(a, m, prev)] else: visited[(a, m, prev)] = True for i in range(a, -1, -1): # Continue only if current value is # smaller compared to previous value if i < prev: numWays[(a, m, prev)] += countNumOfWays(a-i, m-1, i) return numWays[(a, m, prev)]# Values of 'a' and 'm' for which# solution is to be found# MAX_CONST is extremely large value# used for first comparison in the functiona, m, MAX_CONST = 7, 5, 10**5print(countNumOfWays(a, m, MAX_CONST)) |
Javascript
// Javascript code to calculate the number of ways// in which a given number can be represented// as set of finite numbers// Import function to initialize the dictionaryconst visited = new Map();const numWays = new Map();// This function returns the total number// of sets which satisfy given criteria// a --> number to be divided into sets// m --> maximum possible size of the set// x --> previously selected valuefunction countNumOfWays(a, m, prev) { // number is divided properly and // hence solution is obtained if (a == 0) { return 1; } // Solution can't be obtained else if (a > 0 && m == 0) { return 0; } // Return the solution if it has // already been calculated else if (visited.has([a, m, prev])) { return numWays.get([a, m, prev]); } else { visited.set([a, m, prev], true); let totalWays = 0; for (let i = a; i >= 0; i--) { // Continue only if current value is // smaller compared to previous value if (i < prev) { totalWays += countNumOfWays(a - i, m - 1, i); } } numWays.set([a, m, prev], totalWays); return totalWays; }}// Values of 'a' and 'm' for which// solution is to be found// MAX_CONST is extremely large value// used for first comparison in the functionconst a = 7, m = 5, MAX_CONST = 10 ** 5;console.log(countNumOfWays(a, m, MAX_CONST)); |
Java
import java.util.*;public class Main { // Initialize dictionary which is used // to check if given solution is already // visited or not to avoid // calculating it again static Map<String, Boolean> visited = new HashMap<>(); // Initialize dictionary which is used to // store the number of ways in which solution // can be obtained for given values static Map<String, Integer> numWays = new HashMap<>(); // This function returns the total number // of sets which satisfy given criteria // a --> number to be divided into sets // m --> maximum possible size of the set // x --> previously selected value static int countNumOfWays(int a, int m, int prev) { // number is divided properly and // hence solution is obtained if (a == 0) return 1; // Solution can't be obtained if (a > 0 && m == 0) return 0; // Return the solution if it has // already been calculated String key = a + "|" + m + "|" + prev; if (visited.containsKey(key)) return numWays.get(key); visited.put(key, true); int ways = 0; for (int i = a; i >= 0; i--) { // Continue only if current value is // smaller compared to previous value if (i < prev) ways += countNumOfWays(a - i, m - 1, i); } numWays.put(key, ways); return ways; } // Values of 'a' and 'm' for which // solution is to be found static int a = 7, m = 5, MAX_CONST = 10^5; // Driver code public static void main(String[] args) { System.out.println(countNumOfWays(a, m, MAX_CONST)); } } |
C#
using System;using System.Collections.Generic;class GFG{ // Initialize dictionary which is used // to check if given solution is already // visited or not to avoid // calculating it again static Dictionary<string, bool> visited = new Dictionary<string, bool>(); // Initialize dictionary which is used to // store the number of ways in which solution // can be obtained for given values static Dictionary<string, int> numWays = new Dictionary<string, int>(); // This function returns the total number // of sets which satisfy given criteria // a --> number to be divided into sets // m --> maximum possible size of the set // x --> previously selected value static int CountNumOfWays(int a, int m, int prev) { // number is divided properly and // hence solution is obtained if (a == 0) return 1; // Solution can't be obtained if (a > 0 && m == 0) return 0; // Return the solution if it has // already been calculated string key = a + "|" + m + "|" + prev; if (visited.ContainsKey(key)) return numWays[key]; visited.Add(key, true); int ways = 0; for (int i = a; i >= 0; i--) { // Continue only if current value is // smaller compared to previous value if (i < prev) ways += CountNumOfWays(a - i, m - 1, i); } numWays.Add(key, ways); return ways; } // Values of 'a' and 'm' for which // solution is to be found static int a = 7, m = 5, MAX_CONST = (int)Math.Pow(10, 5); // Driver code public static void Main(string[] args) { Console.WriteLine(CountNumOfWays(a, m, MAX_CONST)); }} |
Output:
5
Time Complexity: O(a*log(a))
Auxiliary Space: O(a)
