Posted on by Kalkicode
Code Dynamic Programming

# Count all distinct combinations of sum x using n natural number

In certain problem-solving scenarios, it is necessary to find the count of distinct combinations of natural numbers that sum up to a given value. This article explores the programs that efficiently calculates the number of distinct combinations using a dynamic programming approach. We will provide an explanation of the problem statement and a step-by-step breakdown of the solution implemented in the provided C code.

## Problem Statement

Given two integers, n and x, the task is to count the number of distinct combinations of n natural numbers that add up to the value x. The combinations must be unique, and repetition of numbers within a combination is not allowed. For example, if n = 3 and x = 10, the program should calculate the number of distinct combinations of natural numbers [1, 2, 3] that sum up to 10.

## Solution Approach

To solve this problem, we can use a dynamic programming approach. We create an array called dp of size x+1 to store the number of distinct combinations for each possible sum from 0 to x. The value dp[i] represents the number of distinct combinations that sum up to i.

We initialize all elements of dp to 0, except for dp[0], which is set to 1. This initialization ensures that we have at least one combination for the sum of 0, which is an empty combination.

Next, we iterate from 1 to n to consider each natural number as a potential candidate for combinations. For each number i, we iterate from i to x, updating the dp array. The update is performed using the equation dp[j] = dp[j] + dp[j - i], where dp[j] represents the number of combinations that sum up to j. By adding dp[j - i], we account for the combinations that include the current number i.

Finally, the value of dp[x] represents the count of distinct combinations of n natural numbers that add up to x.

## Code Solution

``````// C Program
// Count all distinct combinations of sum x using n natural number
#include <stdio.h>

void combination(int x, int n)
{
if (n <= 0 || x <= 0)
{
return;
}
printf(" Given n : %d  x : %d \n ", n, x);
int dp[x + 1];
// Set initial value
for (int i = 0; i <= x; ++i)
{
dp[i] = 0;
}
// First value
dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = i; j <= x; ++j)
{
// Update element
dp[j] = dp[j] + dp[j - i];
}
}
// Display calculated result
printf("Possible Combination : %d\n", dp[x]);
}
int main()
{
// n = 3 means use [1,2,3]
int n = 3;
// Sum x = 10
int x = 10;
/*

3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
combination(x, n);
return 0;
}``````

#### Output

`````` Given n : 3  x : 10
Possible Combination : 14``````
``````// Java program for
// Count all distinct combinations of sum x using n natural number
class CountCombination
{
public void combination(int x, int n)
{
if (n <= 0 || x <= 0)
{
return;
}
System.out.println(" Given n : " + n + " x : " + x);
int[] dp = new int[x + 1];
// Set initial value
for (int i = 0; i <= x; ++i)
{
dp[i] = 0;
}
// First value
dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = i; j <= x; ++j)
{
// Update element
dp[j] = dp[j] + dp[j - i];
}
}
// Display calculated result
System.out.println("Possible Combination : " + dp[x]);
}
public static void main(String[] args)
{
// n = 3 means use [1,2,3]
int n = 3;
// Sum x = 10
int x = 10;
/*

3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}
}``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````
``````// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Count all distinct combinations of sum x using n natural number
class CountCombination
{
public: void combination(int x, int n)
{
if (n <= 0 || x <= 0)
{
return;
}
cout << " Given n : " << n << " x : " << x << endl;
int dp[x + 1];
// Set initial value
for (int i = 0; i <= x; ++i)
{
dp[i] = 0;
}
// First value
dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = i; j <= x; ++j)
{
// Update element
dp[j] = dp[j] + dp[j - i];
}
}
// Display calculated result
cout << " Possible Combination : " << dp[x] << endl;
}
};
int main()
{
// n = 3 means use [1,2,3]
int n = 3;
// Sum x = 10
int x = 10;
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
return 0;
}``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````
``````package main
import "fmt"
// Go program for
// Count all distinct combinations of sum x using n natural number
type CountCombination struct {}
func getCountCombination() * CountCombination {
var me *CountCombination = &CountCombination {}
return me
}
func(this CountCombination) combination(x, n int) {
if n <= 0 || x <= 0 {
return
}
fmt.Println(" Given n : ", n, " x : ", x)
var dp = make([] int, x + 1)
// Set initial value
for i := 0 ; i <= x ; i++ {
dp[i] = 0
}
// First value
dp[0] = 1
for i := 1 ; i <= n ; i++ {
for j := i ; j <= x ; j++ {
// Update element
dp[j] = dp[j] + dp[j - i]
}
}
// Display calculated result
fmt.Println("Possible Combination : ", dp[x])
}
func main() {
var task * CountCombination = getCountCombination()
// n = 3 means use [1,2,3]
var n int = 3
// Sum x = 10
var x int = 10
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````
``````// Include namespace system
using System;
// Csharp program for
// Count all distinct combinations of sum x using n natural number
public class CountCombination
{
public void combination(int x, int n)
{
if (n <= 0 || x <= 0)
{
return;
}
Console.WriteLine(" Given n : " + n + " x : " + x);
int[] dp = new int[x + 1];
// Set initial value
for (int i = 0; i <= x; ++i)
{
dp[i] = 0;
}
// First value
dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = i; j <= x; ++j)
{
// Update element
dp[j] = dp[j] + dp[j - i];
}
}
// Display calculated result
Console.WriteLine(" Possible Combination : " + dp[x]);
}
public static void Main(String[] args)
{
// n = 3 means use [1,2,3]
int n = 3;
// Sum x = 10
int x = 10;
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}
}``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````
``````<?php
// Php program for
// Count all distinct combinations of sum x using n natural number
class CountCombination
{
public	function combination(\$x, \$n)
{
if (\$n <= 0 || \$x <= 0)
{
return;
}
echo(" Given n : ".\$n.
" x : ".\$x.
"\n");
\$dp = array_fill(0, \$x + 1, 0);
// First value
\$dp[0] = 1;
for (\$i = 1; \$i <= \$n; ++\$i)
{
for (\$j = \$i; \$j <= \$x; ++\$j)
{
// Update element
\$dp[\$j] = \$dp[\$j] + \$dp[\$j - \$i];
}
}
// Display calculated result
echo(" Possible Combination : ".\$dp[\$x].
"\n");
}
}

function main()
{
// n = 3 means use [1,2,3]
\$n = 3;
// Sum x = 10
\$x = 10;
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}
main();``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````
``````// Node JS program for
// Count all distinct combinations of sum x using n natural number
class CountCombination
{
combination(x, n)
{
if (n <= 0 || x <= 0)
{
return;
}
console.log(" Given n : " + n + " x : " + x);
var dp = Array(x + 1).fill(0);
// First value
dp[0] = 1;
for (var i = 1; i <= n; ++i)
{
for (var j = i; j <= x; ++j)
{
// Update element
dp[j] = dp[j] + dp[j - i];
}
}
// Display calculated result
console.log(" Possible Combination : " + dp[x]);
}
}

function main()
{
// n = 3 means use [1,2,3]
var n = 3;
// Sum x = 10
var x = 10;
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}
main();``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````
``````#  Python 3 program for
#  Count all distinct combinations of sum x using n natural number
class CountCombination :
def combination(self, x, n) :
if (n <= 0 or x <= 0) :
return

print(" Given n : ", n ," x : ", x)
dp = [0] * (x + 1)
#  First value
dp[0] = 1
i = 1
while (i <= n) :
j = i
while (j <= x) :
#  Update element
dp[j] = dp[j] + dp[j - i]
j += 1

i += 1

#  Display calculated result
print(" Possible Combination : ", dp[x])

def main() :
#  n = 3 means use [1,2,3]
n = 3
#  Sum x = 10
x = 10
#    3 3 3 1
#    3 3 2 2
#    3 3 2 1 1
#    3 3 1 1 1 1
#    3 2 2 2 1
#    3 2 2 1 1 1
#    3 2 1 1 1 1 1
#    3 1 1 1 1 1 1 1
#    2 2 2 2 2
#    2 2 2 2 1 1
#    2 2 2 1 1 1 1
#    2 2 1 1 1 1 1 1
#    2 1 1 1 1 1 1 1 1
#    1 1 1 1 1 1 1 1 1 1
#    ---------------------
#    Output : 14

if __name__ == "__main__": main()``````

#### Output

`````` Given n :  3  x :  10
Possible Combination :  14``````
``````#  Ruby program for
#  Count all distinct combinations of sum x using n natural number
class CountCombination
def combination(x, n)
if (n <= 0 || x <= 0)
return
end

print(" Given n : ", n ," x : ", x, "\n")
dp = Array.new(x + 1) {0}
#  First value
dp[0] = 1
i = 1
while (i <= n)
j = i
while (j <= x)
#  Update element
dp[j] = dp[j] + dp[j - i]
j += 1
end

i += 1
end

#  Display calculated result
print(" Possible Combination : ", dp[x], "\n")
end

end

def main()
#  n = 3 means use [1,2,3]
n = 3
#  Sum x = 10
x = 10
#    3 3 3 1
#    3 3 2 2
#    3 3 2 1 1
#    3 3 1 1 1 1
#    3 2 2 2 1
#    3 2 2 1 1 1
#    3 2 1 1 1 1 1
#    3 1 1 1 1 1 1 1
#    2 2 2 2 2
#    2 2 2 2 1 1
#    2 2 2 1 1 1 1
#    2 2 1 1 1 1 1 1
#    2 1 1 1 1 1 1 1 1
#    1 1 1 1 1 1 1 1 1 1
#    ---------------------
#    Output : 14
end

main()``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14
``````
``````// Scala program for
// Count all distinct combinations of sum x using n natural number
class CountCombination()
{
def combination(x: Int, n: Int): Unit = {
if (n <= 0 || x <= 0)
{
return;
}
println(" Given n : " + n + " x : " + x);
var dp: Array[Int] = Array.fill[Int](x + 1)(0);
// First value
dp(0) = 1;
var i: Int = 1;
while (i <= n)
{
var j: Int = i;
while (j <= x)
{
// Update element
dp(j) = dp(j) + dp(j - i);
j += 1;
}
i += 1;
}
// Display calculated result
println(" Possible Combination : " + dp(x));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: CountCombination = new CountCombination();
// n = 3 means use [1,2,3]
var n: Int = 3;
// Sum x = 10
var x: Int = 10;
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}
}``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````
``````// Swift 4 program for
// Count all distinct combinations of sum x using n natural number
class CountCombination
{
func combination(_ x: Int, _ n: Int)
{
if (n <= 0 || x <= 0)
{
return;
}
print(" Given n : ", n ," x : ", x);
var dp: [Int] = Array(repeating: 0, count: x + 1);
// First value
dp[0] = 1;
var i: Int = 1;
while (i <= n)
{
var j: Int = i;
while (j <= x)
{
// Update element
dp[j] = dp[j] + dp[j - i];
j += 1;
}
i += 1;
}
// Display calculated result
print(" Possible Combination : ", dp[x]);
}
}
func main()
{
// n = 3 means use [1,2,3]
let n: Int = 3;
// Sum x = 10
let x: Int = 10;
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}
main();``````

#### Output

`````` Given n :  3  x :  10
Possible Combination :  14``````
``````// Kotlin program for
// Count all distinct combinations of sum x using n natural number
class CountCombination
{
fun combination(x: Int, n: Int): Unit
{
if (n <= 0 || x <= 0)
{
return;
}
println(" Given n : " + n + " x : " + x);
var dp: Array < Int > = Array(x + 1)
{
0
};
// First value
dp[0] = 1;
var i: Int = 1;
while (i <= n)
{
var j: Int = i;
while (j <= x)
{
// Update element
dp[j] = dp[j] + dp[j - i];
j += 1;
}
i += 1;
}
// Display calculated result
println(" Possible Combination : " + dp[x]);
}
}
fun main(args: Array < String > ): Unit
{
// n = 3 means use [1,2,3]
val n: Int = 3;
// Sum x = 10
val x: Int = 10;
/*
3 3 3 1
3 3 2 2
3 3 2 1 1
3 3 1 1 1 1
3 2 2 2 1
3 2 2 1 1 1
3 2 1 1 1 1 1
3 1 1 1 1 1 1 1
2 2 2 2 2
2 2 2 2 1 1
2 2 2 1 1 1 1
2 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
---------------------
Output : 14
*/
}``````

#### Output

`````` Given n : 3 x : 10
Possible Combination : 14``````

## Step-by-Step Explanation of the Code:

1. The function `combination` takes two parameters: x (the target sum) and n (the number of natural numbers).
2. We check if either n or x is less than or equal to 0. If true, we return, as there are no valid combinations possible.
3. We declare an integer array dp of size x+1 to store the number of combinations for each sum.
4. We initialize all elements of dp to 0 using a for loop.
5. We set dp[0] to 1, as there is one empty combination that sums up to 0.
6. We use two nested for loops. The outer loop iterates from 1 to n, representing the numbers used for combinations.
7. The inner loop iterates from i to x, representing the possible sums.
8. Inside the inner loop, we update the dp array using the equation dp[j] = dp[j] + dp[j - i].
9. Finally, we print the value of dp[x], which represents the count of distinct combinations that sum up to x.
10. In the `main` function, we set the values of n and x to 3 and 10, respectively, as an example.
11. We call the `combination` function with the given values of n and x.
12. The program prints the intermediate steps and the final result, which is 14 in this case.

Program efficiently solves the problem of counting distinct combinations of n natural numbers that sum up to a given value x. By utilizing a dynamic programming approach, the program achieves a time complexity of O(n*x), where n represents the number of natural numbers and x represents the target sum. The step-by-step explanation provided in this article should help you understand the logic and implementation of the solution. Feel free to experiment with different values of n and x to explore the versatility of this program.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post