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)
    {
        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

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.

New Comment