Skip to main content

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
Last updated on by Kalkicode




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.

New Comment