What is the relationship between nCr and nPr?

Permutation (nPr) is the process of putting the elements of a group or set in a specific order. Combination (nCr) is the process of selecting elements from a group or set in which the order of the elements is irrelevant.

Is it true that factorials are always even?

Every number greater than one has at least one multiple of two in its factorial, so all other factorials are even.

What is the benefit of taking a greedy approach?

The benefit of using a greedy algorithm is that solutions to smaller problem instances can be simple and straightforward. The disadvantage is that even the best short-term solutions may result in the worst possible long-term outcome.

What exactly is a binomial coefficient?

The binomial coefficient, also known as a combination or a combinatorial number, is the number of ways to choose unordered outcomes from a set of possibilities. Binomial coefficients are denoted by the symbols, which are sometimes read as " choose ".

Table of contents

Introduction

1.1.

Problem statement

1.2.

Sample Examples

Naive approach

2.1.

Steps of algorithm

2.2.

Implementation in C++

2.2.1.

Complexity Analysis

Efficient approach

3.1.

Implementation in C++

3.1.1.

Complexity Analysis

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Count of all the possible combinations of K numbers that sum up to N

Author Sandeep kamila

Introduction

Problem statement

We are given a number N and K. Our task is to count the combinations of K numbers from 1 to N having a sum equal to N. Duplicates are allowed.

Sample Examples

Example 1:

Input: N = 5, K = 2
Output: 4

Explanation:
Combinations are: (1, 4), (4, 1), (2, 3), (3, 2)

Example 2:

Input: N = 3, K = 3
Output: 1

Explanation:
There can be only one combination = (1, 1, 1)

Naive approach

The idea is simple, run a loop from 1 to N and for every number, recursively count the number of combinations after including that number in one of the K numbers.

Finally, add all of these combinations to get the answer.

Steps of algorithm

Create a possible_comb() function which will accept 4 parameters that are N, K, sum and memo. Here N is the required sum, K is the number of elements used, the sum is the sum of numbers till now, and the memo is the matrix to memoise the result. Initially sum = 0, and the memo matrix of size (N+1) * (K+1) is filled with -1.
Check for the base cases:
- If the sum = N and K = 0, then return 1.
- If the sum >= N and K >= 0, then return 0.
Run a loop from 1 to N and count the combinations after including the current number in one of the K numbers.
Add all the combinations and store them in the count variable.
Finally, store the count in the memo matrix and return the value of count, which is the count of the combination of K numbers that sum up to N.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int possible_comb(int N, int K, int sum, vector<vector<int> >& memo)
{
    // 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 answer is already present in memo
    if (memo[sum][K] != -1) {
        return memo[sum][K];
    }

    int count = 0;

    for (int i = 1; i <= N; i++) {
        count = count + possible_comb(N, K - 1, sum + i, memo);
    }

    memo[sum][K] = count;

    return memo[sum][K];
}

int main()
{
    int N = 5, K = 2;

    // memo matrix
    vector<vector<int> > memo(N + 1, vector<int>(K + 1, -1));
    
    cout << possible_comb(N, K, 0, memo);
}

Output:

Complexity Analysis

Time complexity: O(N*K), as we are using a loop from 1 to N and inside the loop, we are counting combinations of the K numbers.

Space complexity: O(N*K), as we are using a memo matrix of size (N+1) * (K+1)

Efficient approach

This approach will use the binomial theorem to solve the problem efficiently.

As the required sum of the K numbers is N, let’s suppose the K numbers are as following:

a1 + a2 + a3 + a4 + a5 + …….. + aK = N

So, according to the binomial theorem, the total number of combinations of K numbers that sum up to N is ^N+K-1C _K-1, where K >= 0.

^NC _K = N! / K! * (N - K)!, here n! denotes the factorial of n and the value of n! = n * (n-1) * (n-2) * (n-3) …… * 1

But in our problem, K >= 1.

So, therefore substitute N with N-K in the above equation, and the equation becomes ^N-K+K-1C _K-1 = ^N-1C _K-1

^N-1C _K-1 = (N-1)! / (K-1)! * (N-1-K+1)! = (N-1)! / (K-1)! * (N-K)!

Implementation in C++

#include <iostream>
using namespace std;

int fact(int n)
{
    if (n == 0)
        return 1;

    return n * fact(n - 1);
}

int possible_comb(int N, int K)
{

    if (N < K)
        return 0;

    return fact(N - 1) / (fact(K - 1) * fact(N - K));
}

int main()
{
    int N = 5;
    int K = 2;

    cout << possible_comb(N, K);

    return 0;
}

Output:

Complexity Analysis

Time complexity: O(N), as we find the factorial of a number N equals 1 * 2 * 3 * 4 ……. N.

Space complexity: O(1), as we are using constant extra space.
Check out this problem - Subarray Sum Divisible By K

Frequently Asked Questions

What is the relationship between nCr and nPr?
Permutation (nPr) is the process of putting the elements of a group or set in a specific order. Combination (nCr) is the process of selecting elements from a group or set in which the order of the elements is irrelevant.
Is it true that factorials are always even?
Every number greater than one has at least one multiple of two in its factorial, so all other factorials are even.
What is the benefit of taking a greedy approach?
The benefit of using a greedy algorithm is that solutions to smaller problem instances can be simple and straightforward. The disadvantage is that even the best short-term solutions may result in the worst possible long-term outcome.
What exactly is a binomial coefficient?
The binomial coefficient, also known as a combination or a combinatorial number, is the number of ways to choose unordered outcomes from a set of possibilities. Binomial coefficients are denoted by the symbols, which are sometimes read as " choose ".

Key Takeaways

This article discussed the different approaches to count all the possible combinations of K numbers that sum up to N with examples and their implementation in C++.

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!

Thank you for reading!