Given a number N, the task is to count the combinations of K numbers from 1 to N having a sum equal to N, with duplicates allowed.
Example:
Input: N = 7, K = 3
Output:15
Explanation:The combinations which lead to the sum N = 7 are: {1, 1, 5}, {1, 5, 1}, {5, 1, 1}, {2, 1, 4}, {1, 2, 4}, {1, 4, 2}, {2, 4, 1}, {4, 1, 2}, {4, 2, 1}, {3, 1, 3}, {1, 3, 3}, {3, 3, 1}, {2, 2, 3}, {2, 3, 2}, {3, 2, 2}Input: N = 5, K = 5
Output: 1
Explanation: {1, 1, 1, 1, 1} is the only combination.
Naive Approach: This problem can be solved using recursion and then memoising the result to improve time complexity. To solve this problem, follow the below steps:
- Create a function, say countWaysUtil which will accept four parameters that are N, K, sum, and dp. Here N is the sum that K elements are required to have, K is the number of elements consumed, sum is the sum accumulated till now and dp is the matrix to memoise the result. This function will give the number of ways to get the sum in K numbers.
- Now initially call countWaysUtil with arguments N, K, sum=0 and dp as a matrix filled with all -1.
- In each recursive call:
- Check for the base cases:
- If the sum is equal to N and K become 0, then return 1.
- If the sum exceeds N and K is still greater than 0, then return 0.
- Now, run a for loop from 1 to N, to check the result for each outcome.
- Sum all the results in a variable cnt and return cnt after memoising.
- Check for the base cases:
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count// all the possible combinations// of K numbers having sum equals to Nint countWaysUtil(int N, int K, int sum, vector<vector<int> >& dp){ // Base Cases if (sum == N and K == 0) { return 1; } if (sum >= N and K >= 0) { return 0; } if (K < 0) { return 0; } // If the result is already memoised if (dp[sum][K] != -1) { return dp[sum][K]; } // Recursive Calls int cnt = 0; for (int i = 1; i <= N; i++) { cnt += countWaysUtil( N, K - 1, sum + i, dp); } // Returning answer return dp[sum][K] = cnt;}void countWays(int N, int K){ vector<vector<int> > dp(N + 1, vector<int>( K + 1, -1)); cout << countWaysUtil(N, K, 0, dp);}// Driver Codeint main(){ int N = 7, K = 3; countWays(N, K);} |
Java
// Java implementation for the above approachclass GFG { // Function to count // all the possible combinations // of K numbers having sum equals to N static int countWaysUtil(int N, int K, int sum, int[][] dp) { // Base Cases if (sum == N && K == 0) { return 1; } if (sum >= N && K >= 0) { return 0; } if (K < 0) { return 0; } // If the result is already memoised if (dp[sum][K] != -1) { return dp[sum][K]; } // Recursive Calls int cnt = 0; for (int i = 1; i <= N; i++) { cnt += countWaysUtil(N, K - 1, sum + i, dp); } // Returning answer return dp[sum][K] = cnt; } static void countWays(int N, int K) { int[][] dp = new int[N + 1][K + 1]; for (int i = 0; i < N + 1; i++) { for (int j = 0; j < K + 1; j++) { dp[i][j] = -1; } } System.out.print(countWaysUtil(N, K, 0, dp)); } // Driver Code public static void main(String[] args) { int N = 7, K = 3; countWays(N, K); }}// This code is contributed by ukasp. |
Python3
# Python3 program for the above approach# Function to count all the possible # combinations of K numbers having # sum equals to Ndef countWaysUtil(N, K, sum, dp): # Base Cases if (sum == N and K == 0): return 1 if (sum >= N and K >= 0): return 0 if (K < 0): return 0 # If the result is already memoised if (dp[sum][K] != -1): return dp[sum][K] # Recursive Calls cnt = 0 for i in range(1, N+1): cnt += countWaysUtil(N, K - 1, sum + i, dp) # Returning answer dp[sum][K] = cnt return dp[sum][K]def countWays(N, K): dp = [[-1 for _ in range(K + 1)] for _ in range(N + 1)] print(countWaysUtil(N, K, 0, dp))# Driver Codeif __name__ == "__main__": N = 7 K = 3 countWays(N, K)# This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;class GFG{ // Function to count// all the possible combinations// of K numbers having sum equals to Nstatic int countWaysUtil(int N, int K, int sum, int [,]dp){ // Base Cases if (sum == N && K == 0) { return 1; } if (sum >= N && K >= 0) { return 0; } if (K < 0) { return 0; } // If the result is already memoised if (dp[sum, K] != -1) { return dp[sum, K]; } // Recursive Calls int cnt = 0; for (int i = 1; i <= N; i++) { cnt += countWaysUtil( N, K - 1, sum + i, dp); } // Returning answer return dp[sum, K] = cnt;}static void countWays(int N, int K){ int [,]dp = new int[N + 1, K + 1]; for(int i = 0; i < N + 1; i++) { for(int j = 0; j < K + 1; j++) { dp[i, j] = -1; } } Console.Write(countWaysUtil(N, K, 0, dp));}// Driver Codepublic static void Main(){ int N = 7, K = 3; countWays(N, K);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the above approach// Function to count// all the possible combinations// of K numbers having sum equals to Nfunction countWaysUtil(N, K, sum, dp) { // Base Cases if (sum == N && K == 0) { return 1; } if (sum >= N && K >= 0) { return 0; } if (K < 0) { return 0; } // If the result is already memoised if (dp[sum][K] != -1) { return dp[sum][K]; } // Recursive Calls let cnt = 0; for (let i = 1; i <= N; i++) { cnt += countWaysUtil( N, K - 1, sum + i, dp); } // Returning answer return dp[sum][K] = cnt;}function countWays(N, K) { let dp = new Array(N + 1).fill(0).map(() => new Array(K + 1).fill(-1)) document.write(countWaysUtil(N, K, 0, dp));}// Driver Codelet N = 7, K = 3;countWays(N, K);// This code is contributed by saurabh_jaiswal.</script> |
Output
15
Time Complexity: O(N*K)
Space Complexity: O(N*K)
Efficient Approach: This problem can also be solved using the binomial theorem. As the required sum is N with K elements, so suppose the K numbers are:
a1 + a2 + a3 + a4 + …….. + aK = N
According to the standard principle of partitioning in the binomial theorem, the above equation has a solution which is N+K-1CK-1, where K>=0.
But in our case, K>=1.
So, therefore N should be substituted with N-K and the equation becomes N-1CK-1
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Method to find factorial of given numberint factorial(int n){ if (n == 0) return 1; return n * factorial(n - 1);}// Function to count all the possible // combinations of K numbers having// sum equals to Nint totalWays(int N, int K){ // If N<K if (N < K) return 0; // Storing numerator int n1 = factorial(N - 1); // Storing denominator int n2 = factorial(K - 1) * factorial(N - K); int ans = (n1 / n2); // Returning answer return ans;}// Driver codeint main() { int N = 7; int K = 3; int ans = totalWays(N, K); cout << ans; return 0;}// This code is contributed by Shubham Singh |
C
// C Program for the above approach#include <stdio.h> // method to find factorial of given number int factorial(int n) { if (n == 0) return 1; return n*factorial(n - 1); } // Function to count // all the possible combinations // of K numbers having sum equals to N int totalWays(int N, int K) { // If N<K if (N < K) return 0; // Storing numerator int n1 = factorial(N - 1); // Storing denominator int n2 = factorial(K - 1)*factorial(N - K); int ans = (n1/n2); // Returning answer return ans; } // Driver method int main() { int N = 7; int K = 3; int ans = totalWays(N, K); printf("%d",ans); return 0; } // This code is contributed by Shubham Singh |
Java
// Java Program for the above approachclass Solution{ // method to find factorial of given number static int factorial(int n) { if (n == 0) return 1; return n*factorial(n - 1); } // Function to count // all the possible combinations // of K numbers having sum equals to N static int totalWays(int N, int K) { // If N<K if (N < K) return 0; // Storing numerator int n1 = factorial(N - 1); // Storing denominator int n2 = factorial(K - 1)*factorial(N - K); int ans = (n1/n2); // Returning answer return ans; } // Driver method public static void main(String[] args) { int N = 7; int K = 3; int ans = totalWays(N, K); System.out.println(ans); }}// This code is contributed by umadevi9616 |
Python3
# Python Program for the above approachfrom math import factorialclass Solution: # Function to count # all the possible combinations # of K numbers having sum equals to N def totalWays(self, N, K): # If N<K if (N < K): return 0 # Storing numerator n1 = factorial(N-1) # Storing denominator n2 = factorial(K-1)*factorial(N-K) ans = (n1//n2) # Returning answer return ans# Driver Codeif __name__ == '__main__': N = 7 K = 3 ob = Solution() ans = ob.totalWays(N, K) print(ans) |
C#
// C# Program for the above approachusing System;public class Solution { // method to find factorial of given number static int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } // Function to count // all the possible combinations // of K numbers having sum equals to N static int totalWays(int N, int K) { // If N<K if (N < K) return 0; // Storing numerator int n1 = factorial(N - 1); // Storing denominator int n2 = factorial(K - 1) * factorial(N - K); int ans = (n1 / n2); // Returning answer return ans; } // Driver method public static void Main(String[] args) { int N = 7; int K = 3; int ans = totalWays(N, K); Console.WriteLine(ans); }}// This code is contributed by umadevi9616 |
Javascript
<script>// Javascript program for the above approach// Method to find factorial of given numberfunction factorial(n){ if (n == 0) return 1; return n * factorial(n - 1);}// Function to count all the possible // combinations of K numbers having// sum equals to Nfunction totalWays( N, K){ // If N<K if (N < K) return 0; // Storing numerator let n1 = factorial(N - 1); // Storing denominator let n2 = factorial(K - 1) * factorial(N - K); let ans = (n1 / n2); // Returning answer return ans;}// Driver codelet N = 7;let K = 3;let ans = totalWays(N, K);document.write(ans);// This code is contributed by Shubham Singh</script> |
Output
15
Time complexity: O(N)
Auxiliary Space: O(1)
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!
