Posted on by Kalkicode
Code Mathematics

# Count the number of ways to cover given sum

Counting the number of ways to cover a given sum means finding all the possible combinations of numbers that add up to a given target sum. In the example you provided, the target sum is 5, and we are looking for all possible combinations of numbers that add up to 5.

``````n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5``````

For instance, the first row of the example shows that there is only one way to get a sum of 5 using five 1's. The second row shows that there are two ways to get a sum of 5 using four 1's and one 2. The third row shows that there are two ways to get a sum of 5 using three 1's and one 2. The process continues until we find all possible combinations of numbers that add up to 5.

Counting the number of ways to cover a given sum is a common problem in computer science and is often used in dynamic programming, backtracking, and other algorithms.

## Code Solution

``````/*
C program for
Count the number of ways to cover given sum
*/
#include <stdio.h>
#include <math.h>

// Display number of way to cover given sum
void converSum(int n)
{
int result = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = pow(2, n - 1);
}
// Given number
printf("\n Given Distance : %d", n);
printf("\n Number of ways : %d", result);
}
int main(int argc, char
const *argv[])
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
converSum(5);
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
converSum(6);
return 0;
}``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````// Java program
// Count the number of ways to cover given sum
public class Covering
{
// Display number of way to cover given sum
public void converSum(int n)
{
int result = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = (int)Math.pow(2, n - 1);
}
// Given number
System.out.print("\n Given Distance : " + n);
System.out.print("\n Number of ways : " + result);
}
public static void main(String[] args)
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}
}``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````// Include header file
#include <iostream>
#include <math.h>

using namespace std;
// C++ program
// Count the number of ways to cover given sum
class Covering
{
public:
// Display number of way to cover given sum
void converSum(int n)
{
int result = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = (int) pow(2, n - 1);
}
// Given number
cout << "\n Given Distance : " << n;
cout << "\n Number of ways : " << result;
}
};
int main()
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
return 0;
}``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````// Include namespace system
using System;
// Csharp program
// Count the number of ways to cover given sum
public class Covering
{
// Display number of way to cover given sum
public void converSum(int n)
{
int result = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = (int) Math.Pow(2, n - 1);
}
// Given number
Console.Write("\n Given Distance : " + n);
Console.Write("\n Number of ways : " + result);
}
public static void Main(String[] args)
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}
}``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````package main
import "math"
import "fmt"
// Go program
// Count the number of ways to cover given sum
type Covering struct {}
func getCovering() * Covering {
var me *Covering = &Covering {}
return me
}
// Display number of way to cover given sum
func(this Covering) converSum(n int) {
var result int = 0
if n > 0 {
// Formula = 2^(n-1)
result = int(math.Pow(2.0, float64(n) - 1.0))
}
// Given number
fmt.Print("\n Given Distance : ", n)
fmt.Print("\n Number of ways : ", result)
}
func main() {
var task * Covering = getCovering()
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````<?php
// Php program
// Count the number of ways to cover given sum
class Covering
{
// Display number of way to cover given sum
public	function converSum(\$n)
{
\$result = 0;
if (\$n > 0)
{
// Formula = 2^(n-1)
\$result = (int) pow(2, \$n - 1);
}
// Given number
echo("\n Given Distance : ".\$n);
echo("\n Number of ways : ".\$result);
}
}

function main()
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}
main();``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````// Node JS program
// Count the number of ways to cover given sum
class Covering
{
// Display number of way to cover given sum
converSum(n)
{
var result = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = parseInt(Math.pow(2, n - 1));
}
// Given number
process.stdout.write("\n Given Distance : " + n);
process.stdout.write("\n Number of ways : " + result);
}
}

function main()
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}
main();``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````import math
#  Python 3 program
#  Count the number of ways to cover given sum
class Covering :
#  Display number of way to cover given sum
def converSum(self, n) :
result = 0
if (n > 0) :
#  Formula = 2^(n-1)
result = int(2 ** (n - 1))

#  Given number
print("\n Given Distance : ", n, end = "")
print("\n Number of ways : ", result, end = "")

def main() :
#    Distance n = 5
#  -------------------
#    1  1  1  1  1
#    1  1  1  2
#    1  1  2  1
#    1  1  3
#    1  2  1  1
#    1  2  2
#    1  3  1
#    1  4
#    2  1  1  1
#    2  1  2
#    2  2  1
#    2  3
#    3  1  1
#    3  2
#    4  1
#    5
#    Distance n = 6
#  -------------------
#    1  1  1  1  1  1
#    1  1  1  1  2
#    1  1  1  2  1
#    1  1  1  3
#    1  1  2  1  1
#    1  1  2  2
#    1  1  3  1
#    1  1  4
#    1  2  1  1  1
#    1  2  1  2
#    1  2  2  1
#    1  2  3
#    1  3  1  1
#    1  3  2
#    1  4  1
#    1  5
#    2  1  1  1  1
#    2  1  1  2
#    2  1  2  1
#    2  1  3
#    2  2  1  1
#    2  2  2
#    2  3  1
#    2  4
#    3  1  1  1
#    3  1  2
#    3  2  1
#    3  3
#    4  1  1
#    4  2
#    5  1
#    6

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

#### Output

`````` Given Distance :  5
Number of ways :  16
Given Distance :  6
Number of ways :  32``````
``````#  Ruby program
#  Count the number of ways to cover given sum
class Covering
#  Display number of way to cover given sum
def converSum(n)
result = 0
if (n > 0)
#  Formula = 2^(n-1)
result = (2 ** (n - 1)). to_i
end

#  Given number
print("\n Given Distance : ", n)
print("\n Number of ways : ", result)
end

end

def main()
#    Distance n = 5
#  -------------------
#    1  1  1  1  1
#    1  1  1  2
#    1  1  2  1
#    1  1  3
#    1  2  1  1
#    1  2  2
#    1  3  1
#    1  4
#    2  1  1  1
#    2  1  2
#    2  2  1
#    2  3
#    3  1  1
#    3  2
#    4  1
#    5
#    Distance n = 6
#  -------------------
#    1  1  1  1  1  1
#    1  1  1  1  2
#    1  1  1  2  1
#    1  1  1  3
#    1  1  2  1  1
#    1  1  2  2
#    1  1  3  1
#    1  1  4
#    1  2  1  1  1
#    1  2  1  2
#    1  2  2  1
#    1  2  3
#    1  3  1  1
#    1  3  2
#    1  4  1
#    1  5
#    2  1  1  1  1
#    2  1  1  2
#    2  1  2  1
#    2  1  3
#    2  2  1  1
#    2  2  2
#    2  3  1
#    2  4
#    3  1  1  1
#    3  1  2
#    3  2  1
#    3  3
#    4  1  1
#    4  2
#    5  1
#    6
end

main()``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````// Scala program
// Count the number of ways to cover given sum
class Covering()
{
// Display number of way to cover given sum
def converSum(n: Int): Unit = {
var result: Int = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = Math.pow(2, n - 1).toInt;
}
// Given number
print("\n Given Distance : " + n);
print("\n Number of ways : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Covering = new Covering();
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}
}``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````
``````import Foundation;
// Swift 4 program
// Count the number of ways to cover given sum
class Covering
{
// Display number of way to cover given sum
func converSum(_ n: Int)
{
var result: Int = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = Int(pow(2.0, Double(n) - 1.0));
}
// Given number
print("\n Given Distance : ", n, terminator: "");
print("\n Number of ways : ", result, terminator: "");
}
}
func main()
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}
main();``````

#### Output

`````` Given Distance :  5
Number of ways :  16
Given Distance :  6
Number of ways :  32``````
``````// Kotlin program
// Count the number of ways to cover given sum
class Covering
{
// Display number of way to cover given sum
fun converSum(n: Int): Unit
{
var result: Int = 0;
if (n > 0)
{
// Formula = 2^(n-1)
result = Math.pow(2.0, n - 1.0).toInt();
}
// Given number
print("\n Given Distance : " + n);
print("\n Number of ways : " + result);
}
}
fun main(args: Array < String > ): Unit
{
/*
Distance n = 5
-------------------
1  1  1  1  1
1  1  1  2
1  1  2  1
1  1  3
1  2  1  1
1  2  2
1  3  1
1  4
2  1  1  1
2  1  2
2  2  1
2  3
3  1  1
3  2
4  1
5
*/
/*
Distance n = 6
-------------------
1  1  1  1  1  1
1  1  1  1  2
1  1  1  2  1
1  1  1  3
1  1  2  1  1
1  1  2  2
1  1  3  1
1  1  4
1  2  1  1  1
1  2  1  2
1  2  2  1
1  2  3
1  3  1  1
1  3  2
1  4  1
1  5
2  1  1  1  1
2  1  1  2
2  1  2  1
2  1  3
2  2  1  1
2  2  2
2  3  1
2  4
3  1  1  1
3  1  2
3  2  1
3  3
4  1  1
4  2
5  1
6
*/
}``````

#### Output

`````` Given Distance : 5
Number of ways : 16
Given Distance : 6
Number of ways : 32``````

## 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