Horje
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
7 

Input: 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)

 


 


Reffered: https://www.geeksforgeeks.org

Combinatorial

Related
Number of ways to divide a N elements equally into group of at least 2 Number of ways to divide a N elements equally into group of at least 2
Count all possible pairs in given Array with product K Count all possible pairs in given Array with product K
Maximize count of 001 and 110 that can be formed using M 0s and N 1s Maximize count of 001 and 110 that can be formed using M 0s and N 1s
Java Program for Counting sets of 1s and 0s in a binary matrix Java Program for Counting sets of 1s and 0s in a binary matrix
Python Program for Counting sets of 1s and 0s in a binary matrix Python Program for Counting sets of 1s and 0s in a binary matrix

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje