Count all distinct combinations of sum x using n natural number
Here given code implementation process.
// 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)
{
CountCombination task = new CountCombination();
// 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
*/
task.combination(x, n);
}
}
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()
{
CountCombination *task = new CountCombination();
// 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
*/
task->combination(x, n);
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
*/
task.combination(x, n)
}
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)
{
CountCombination task = new CountCombination();
// 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
*/
task.combination(x, n);
}
}
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()
{
$task = new CountCombination();
// 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
*/
$task->combination($x, $n);
}
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()
{
var task = new CountCombination();
// 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
*/
task.combination(x, n);
}
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() :
task = CountCombination()
# 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
task.combination(x, n)
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()
task = CountCombination.new()
# 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
task.combination(x, n)
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
*/
task.combination(x, n);
}
}
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()
{
let task: CountCombination = CountCombination();
// 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
*/
task.combination(x, n);
}
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
{
val task: CountCombination = CountCombination();
// 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
*/
task.combination(x, n);
}
Output
Given n : 3 x : 10
Possible Combination : 14
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.
New Comment