Count of all valid combinations of at most K numbers that sum up to N
Given two numbers N and K, the task is to find the count of all valid combinations of at most K numbers that sum up to N such that the following conditions are true:
- Only numbers 1 through 9 are used.
- Each number is used at most once.
Examples:
Input: K = 3, N = 7
Output: 5
Explanation:
1 2 4
1 6
2 5
3 4
7Input: K = 3, N = 9
Output: 8
Explanation:
1 2 6
1 3 5
1 8
2 3 4
2 7
3 6
4 5
9
Naive Approach: The idea is to create an array of numbers from 1 to 9, and find the count of all subsequences of length at most K with sum N.
Time Complexity: O(10^2)
Auxiliary Space: O(1)
Recursive Approach: The problem can also be solved using Recursion as follows:
- Create an array of digits 1-9 in arr.
- Create recursion function that iterates the array with current index as i, current sum as sum, current count as c, and resultant count of combinations as ans.
- Base case 1: if (sum == n && c <= k)
- Increment resultant count of combinations ans
- Return the ans
- Base case 2: if (i >= arr.size() || sum > n || c > k)
- Return the ans
- Else
- Push current array element into temp vector
- Call the recursive function
- Pop the current element from the vector
- Call the recursive function
Below is the implementation of the above approach:
C++
// C++ code to solve the above problem #include <algorithm> #include <cmath> #include <cstdio> #include <iostream> #include <vector> using namespace std; // Recursive program to find count of // all combinations of at most K // digits with sum N int rec(vector< int >& arr, int i, int k, int c, int n, int & ans, int sum) { // Base case 1 if (sum == n && c <= k) { ans++; return ans; } // Base case 2 if (i >= arr.size() || sum > n || c > k) return ans; // Consider arr[i] into current selection // and call recursive function ans = rec(arr, i + 1, k, c + 1, n, ans, sum + arr[i]); // Do not consider arr[i] into current // selection and call recursive function ans = rec(arr, i + 1, k, c, n, ans, sum); return ans; } // Function to solve the problem // and print the count of combinations int combinationSum( int k, int n) { vector< int > arr(9, 0); for ( int i = 1; i <= 9; i++) arr[i - 1] = i; int ans; // Recursive function call ans = rec(arr, 0, k, 0, n, ans, 0); return ans; } // Driver Code int main() { int N = 9, K = 3; cout << combinationSum(K, N) << endl; return 0; } |
Java
// JAVA code to solve the above problem import java.util.*; class GFG { // Recursive program to find count of // all combinations of at most K // digits with sum N public static int rec( int [] arr, int i, int k, int c, int n, int ans, int sum) { // Base case 1 if (sum == n && c <= k) { ans++; return ans; } // Base case 2 if (i >= arr.length || sum > n || c > k) return ans; // Consider arr[i] into current selection // and call recursive function ans = rec(arr, i + 1 , k, c + 1 , n, ans, sum + arr[i]); // Do not consider arr[i] into current // selection and call recursive function ans = rec(arr, i + 1 , k, c, n, ans, sum); return ans; } // Function to solve the problem // and print the count of combinations public static int combinationSum( int k, int n) { int [] arr = new int [ 9 ]; for ( int i = 0 ; i < 9 ; i++) { arr[i] = 0 ; } for ( int i = 1 ; i <= 9 ; i++) arr[i - 1 ] = i; int ans = 0 ; // Recursive function call ans = rec(arr, 0 , k, 0 , n, ans, 0 ); return ans; } // Driver Code public static void main(String[] args) { int N = 9 , K = 3 ; System.out.println(combinationSum(K, N)); } } // This code is contributed by Taranpreet |
Python3
# python3 code to solve the above problem # Recursive program to find count of # all combinations of at most K # digits with sum N def rec(arr, i, k, c, n, ans, sum ): # Base case 1 if ( sum = = n and c < = k): ans + = 1 return ans # Base case 2 if (i > = len (arr) or sum > n or c > k): return ans # Consider arr[i] into current selection # and call recursive function ans = rec(arr, i + 1 , k, c + 1 , n, ans, sum + arr[i]) # Do not consider arr[i] into current # selection and call recursive function ans = rec(arr, i + 1 , k, c, n, ans, sum ) return ans # Function to solve the problem # and print the count of combinations def combinationSum(k, n): arr = [ 0 for _ in range ( 9 )] for i in range ( 1 , 10 ): arr[i - 1 ] = i ans = 0 # Recursive function call ans = rec(arr, 0 , k, 0 , n, ans, 0 ) return ans # Driver Code if __name__ = = "__main__" : N, K = 9 , 3 print (combinationSum(K, N)) # This code is contributed by rakeshsahni |
C#
// C# code to solve the above problem using System; class GFG { // Recursive program to find count of // all combinations of at most K // digits with sum N static int rec( int [] arr, int i, int k, int c, int n, int ans, int sum) { // Base case 1 if (sum == n && c <= k) { ans++; return ans; } // Base case 2 if (i >= arr.Length || sum > n || c > k) return ans; // Consider arr[i] into current selection // and call recursive function ans = rec(arr, i + 1, k, c + 1, n, ans, sum + arr[i]); // Do not consider arr[i] into current // selection and call recursive function ans = rec(arr, i + 1, k, c, n, ans, sum); return ans; } // Function to solve the problem // and print the count of combinations static int combinationSum( int k, int n) { int [] arr = new int [9]; for ( int i = 0; i < 9; i++) { arr[i] = 0; } for ( int i = 1; i <= 9; i++) arr[i - 1] = i; int ans = 0; // Recursive function call ans = rec(arr, 0, k, 0, n, ans, 0); return ans; } // Driver Code public static int Main() { int N = 9, K = 3; Console.WriteLine(combinationSum(K, N)); return 0; } } // This code is contributed by Taranpreet |
Javascript
<script> // JavaScript code for the above approach // Recursive program to find count of // all combinations of at most K // digits with sum N function rec(arr, i, k, c, n, ans, sum) { // Base case 1 if (sum == n && c <= k) { ans++; return ans; } // Base case 2 if (i >= arr.length || sum > n || c > k) return ans; // Consider arr[i] into current selection // and call recursive function ans = rec(arr, i + 1, k, c + 1, n, ans, sum + arr[i]); // Do not consider arr[i] into current // selection and call recursive function ans = rec(arr, i + 1, k, c, n, ans, sum); return ans; } // Function to solve the problem // and print the count of combinations function combinationSum(k, n) { let arr = new Array(9).fill(0); for (let i = 1; i <= 9; i++) arr[i - 1] = i; let ans = 0; // Recursive function call ans = rec(arr, 0, k, 0, n, ans, 0); return ans; } // Driver Code let N = 9, K = 3; document.write(combinationSum(K, N) + '<br>' ); // This code is contributed by Potta Lokesh </script> |
Output
8
Time Complexity: O(10^2)
Auxiliary Space: O(10^2)