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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!