Count the minimum number of elements required to given sum

In this article, we will discuss the problem of counting the minimum number of elements required to achieve a given sum. We'll provide a step-by-step explanation of the algorithm and include the pseudocode for better understanding. Additionally, we'll explain the output of the provided code examples along with their time complexity analysis.

Problem Statement

Given an array of positive integers and a target sum, we need to find the minimum number of elements from the array whose sum is equal to the given target sum.

Pseudocode Algorithm

countElements(arr[], n, sum):
    dp[][]     // auxiliary space for dynamic programming
    initialize dp[][] with default values

    for i = 1 to n:
        element = arr[i - 1]
        if element > 0:
            for j = 1 to sum:
                if element > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = minimum(dp[i - 1][j], dp[i][j - element] + 1)

    display given sum
    if dp[n][sum] == sum + 1 or dp[n][sum] == 0:
        print "None"
    else:
        print "Element:", dp[n][sum]

Explanation

The pseudocode outlines the steps to solve the problem. We use dynamic programming to build a 2D array dp[][] as an auxiliary space. The array stores the minimum number of elements required to achieve the given sum at each position. We initialize it with default values.

We iterate through the array arr[] and calculate the minimum number of elements needed for each sum. We consider two cases:

• If the current element is greater than the sum, we skip it.
• If the current element is less than or equal to the sum, we choose the minimum of two possibilities:
  • Excluding the current element: dp[i - 1][j]
  • Including the current element: dp[i][j - element] + 1

After calculating all possible sums, we check the value at dp[n][sum] (where n is the size of the array). If it is either sum + 1 or 0, it means no combination of elements exists to achieve the given sum. Otherwise, we display the minimum number of elements required.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// C program 
// Count the minimum number of elements required to given sum
#include <stdio.h>

// Returns the minimum value of two numbers
int minimum(int a, int b)
{
	if (a < b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
// Handles the request of count minimum elements 
// Sum of array elements which is equal to given sum
void countElements(int arr[], int n, int sum)
{
	if (sum > 0)
	{
		// Auxiliary space
		int dp[n + 1][sum + 1];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		int element = 0;
		// Set default value
		for (i = 0; i <= n; ++i)
		{
			for (j = 0; j <= sum; ++j)
			{
				if (i == 0)
				{
					// Set first row elements
					dp[i][j] = sum + 1;
				}
				else
				{
					dp[i][j] = 0;
				}
			}
		}
		// Calculate result
		// Execute loop through by array size
		for (i = 1; i <= n; i++)
		{
			// Get element
			element = arr[i - 1];
			if (element > 0)
			{
				for (j = 1; j <= sum; ++j)
				{
					if (element > j)
					{
						// When array element is greater than given sum
						dp[i][j] = dp[i - 1][j];
					}
					else
					{
						// When array elements less than given sum
						dp[i][j] = minimum(dp[i - 1][j], dp[i][j - element] + 1);
					}
				}
			}
		}
		// Display given sum
		printf("\n Given Sum : %d", sum);
		if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
		{
			printf("\n None \n");
		}
		else
		{
			printf("\n Element : %d\n", dp[n][sum]);
		}
	}
}
int main()
{
	// Define array of positive integers
	int arr[] = {
		4 , 6 , 2 , 8 , 5
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	// 31 = 8 + 8 + 8 + 5 + 2
	countElements(arr, n, 31);
	// 17 = 6 + 6 + 5
	countElements(arr, n, 17);
	countElements(arr, n, 3);
	return 0;
}

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

/*
    Java Program
    Count the minimum number of elements required to given sum
*/
public class Counting
{
	// Returns the minimum value of two numbers
	public int minimum(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	public void countElements(int[] arr, int n, int sum)
	{
		if (sum > 0)
		{
			// Auxiliary space
			int[][] dp = new int[n + 1][sum + 1];
			// Loop controlling variables
			int i = 0;
			int j = 0;
			int element = 0;
			// Set default value
			for (i = 0; i <= n; ++i)
			{
				for (j = 0; j <= sum; ++j)
				{
					if (i == 0)
					{
						// Set first row elements
						dp[i][j] = sum + 1;
					}
					else
					{
						dp[i][j] = 0;
					}
				}
			}
			// Calculate result
			// Execute loop through by array size
			for (i = 1; i <= n; i++)
			{
				// Get element
				element = arr[i - 1];
				if (element > 0)
				{
					for (j = 1; j <= sum; ++j)
					{
						if (element > j)
						{
							// When array element is greater than given sum
							dp[i][j] = dp[i - 1][j];
						}
						else
						{
							// When array elements less than given sum
							dp[i][j] = minimum(dp[i - 1][j], dp[i][j - element] + 1);
						}
					}
				}
			}
			// Display given sum
			System.out.print("\n Given Sum : " + sum);
			if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
			{
				System.out.print("\n None \n");
			}
			else
			{
				System.out.println("\n Element : " + dp[n][sum]);
			}
		}
	}
	public static void main(String[] args)
	{
		Counting task = new Counting();
		// Define array of positive integers
		int[] arr = {
			4 , 6 , 2 , 8 , 5
		};
		int n = arr.length;
		// 31 = 8 + 8 + 8 + 5 + 2
		task.countElements(arr, n, 31);
		// 17 = 6 + 6 + 5
		task.countElements(arr, n, 17);
		task.countElements(arr, n, 3);
	}
}

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Count the minimum number of elements required to given sum
*/
class Counting
{
	public:
		// Returns the minimum value of two numbers
		int minimum(int a, int b)
		{
			if (a < b)
			{
				return a;
			}
			else
			{
				return b;
			}
		}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	void countElements(int arr[], int n, int sum)
	{
		if (sum > 0)
		{
			// Auxiliary space
			int dp[n + 1][sum + 1];
			// Loop controlling variables
			int i = 0;
			int j = 0;
			int element = 0;
			// Set default value
			for (i = 0; i <= n; ++i)
			{
				for (j = 0; j <= sum; ++j)
				{
					if (i == 0)
					{
						// Set first row elements
						dp[i][j] = sum + 1;
					}
					else
					{
						dp[i][j] = 0;
					}
				}
			}
			// Calculate result
			// Execute loop through by array size
			for (i = 1; i <= n; i++)
			{
				// Get element
				element = arr[i - 1];
				if (element > 0)
				{
					for (j = 1; j <= sum; ++j)
					{
						if (element > j)
						{
							// When array element is greater than given sum
							dp[i][j] = dp[i - 1][j];
						}
						else
						{
							// When array elements less than given sum
							dp[i][j] = this->minimum(dp[i - 1][j], 
                                                     dp[i][j - element] + 1);
						}
					}
				}
			}
			// Display given sum
			cout << "\n Given Sum : " << sum;
			if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
			{
				cout << "\n None \n";
			}
			else
			{
				cout << "\n Element : " << dp[n][sum] << endl;
			}
		}
	}
};
int main()
{
	Counting *task = new Counting();
	// Define array of positive integers
	int arr[] = {
		4 , 6 , 2 , 8 , 5
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	// 31 = 8 + 8 + 8 + 5 + 2
	task->countElements(arr, n, 31);
	// 17 = 6 + 6 + 5
	task->countElements(arr, n, 17);
	task->countElements(arr, n, 3);
	return 0;
}

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

// Include namespace system
using System;
/*
    Csharp Program
    Count the minimum number of elements required to given sum
*/
public class Counting
{
	// Returns the minimum value of two numbers
	public int minimum(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	public void countElements(int[] arr, int n, int sum)
	{
		if (sum > 0)
		{
			// Auxiliary space
			int[,] dp = new int[n + 1,sum + 1];
			// Loop controlling variables
			int i = 0;
			int j = 0;
			int element = 0;
			// Set default value
			for (i = 0; i <= n; ++i)
			{
				for (j = 0; j <= sum; ++j)
				{
					if (i == 0)
					{
						// Set first row elements
						dp[i,j] = sum + 1;
					}
					else
					{
						dp[i,j] = 0;
					}
				}
			}
			// Calculate result
			// Execute loop through by array size
			for (i = 1; i <= n; i++)
			{
				// Get element
				element = arr[i - 1];
				if (element > 0)
				{
					for (j = 1; j <= sum; ++j)
					{
						if (element > j)
						{
							// When array element is greater than given sum
							dp[i,j] = dp[i - 1,j];
						}
						else
						{
							// When array elements less than given sum
							dp[i,j] = this.minimum(dp[i - 1,j], dp[i,j - element] + 1);
						}
					}
				}
			}
			// Display given sum
			Console.Write("\n Given Sum : " + sum);
			if (dp[n,sum] == sum + 1 || dp[n,sum] == 0)
			{
				Console.Write("\n None \n");
			}
			else
			{
				Console.WriteLine("\n Element : " + dp[n,sum]);
			}
		}
	}
	public static void Main(String[] args)
	{
		Counting task = new Counting();
		// Define array of positive integers
		int[] arr = {
			4 , 6 , 2 , 8 , 5
		};
		int n = arr.Length;
		// 31 = 8 + 8 + 8 + 5 + 2
		task.countElements(arr, n, 31);
		// 17 = 6 + 6 + 5
		task.countElements(arr, n, 17);
		task.countElements(arr, n, 3);
	}
}

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

<?php
/*
    Php Program
    Count the minimum number of elements required to given sum
*/
class Counting
{
	// Returns the minimum value of two numbers
	public	function minimum($a, $b)
	{
		if ($a < $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	public	function countElements($arr, $n, $sum)
	{
		if ($sum > 0)
		{
			// Auxiliary space
			$dp = array_fill(0, $sum + 1, array_fill(0, $n + 1, 0));
			// Loop controlling variables
			$i = 0;
			$j = 0;
			$element = 0;
			// Set default value
			for ($i = 0; $i <= $n; ++$i)
			{
				for ($j = 0; $j <= $sum; ++$j)
				{
					if ($i == 0)
					{
						// Set first row elements
						$dp[$i][$j] = $sum + 1;
					}
					else
					{
						$dp[$i][$j] = 0;
					}
				}
			}
			// Calculate result
			// Execute loop through by array size
			for ($i = 1; $i <= $n; $i++)
			{
				// Get element
				$element = $arr[$i - 1];
				if ($element > 0)
				{
					for ($j = 1; $j <= $sum; ++$j)
					{
						if ($element > $j)
						{
							// When array element is greater than given sum
							$dp[$i][$j] = $dp[$i - 1][$j];
						}
						else
						{
							// When array elements less than given sum
							$dp[$i][$j] = $this->minimum($dp[$i - 1][$j], $dp[$i][$j - $element] + 1);
						}
					}
				}
			}
			// Display given sum
			echo("\n Given Sum : ".$sum);
			if ($dp[$n][$sum] == $sum + 1 || $dp[$n][$sum] == 0)
			{
				echo("\n None \n");
			}
			else
			{
				echo("\n Element : ".$dp[$n][$sum].
					"\n");
			}
		}
	}
}

function main()
{
	$task = new Counting();
	// Define array of positive integers
	$arr = array(4, 6, 2, 8, 5);
	$n = count($arr);
	// 31 = 8 + 8 + 8 + 5 + 2
	$task->countElements($arr, $n, 31);
	// 17 = 6 + 6 + 5
	$task->countElements($arr, $n, 17);
	$task->countElements($arr, $n, 3);
}
main();

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

/*
    Node JS Program
    Count the minimum number of elements required to given sum
*/
class Counting
{
	// Returns the minimum value of two numbers
	minimum(a, b)
	{
		if (a < b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	countElements(arr, n, sum)
	{
		if (sum > 0)
		{
			// Auxiliary space
			var dp = Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(0));
			// Loop controlling variables
			var i = 0;
			var j = 0;
			var element = 0;
			// Set default value
			for (i = 0; i <= n; ++i)
			{
				for (j = 0; j <= sum; ++j)
				{
					if (i == 0)
					{
						// Set first row elements
						dp[i][j] = sum + 1;
					}
					else
					{
						dp[i][j] = 0;
					}
				}
			}
			// Calculate result
			// Execute loop through by array size
			for (i = 1; i <= n; i++)
			{
				// Get element
				element = arr[i - 1];
				if (element > 0)
				{
					for (j = 1; j <= sum; ++j)
					{
						if (element > j)
						{
							// When array element is greater than given sum
							dp[i][j] = dp[i - 1][j];
						}
						else
						{
							// When array elements less than given sum
							dp[i][j] = this.minimum(dp[i - 1][j], dp[i][j - element] + 1);
						}
					}
				}
			}
			// Display given sum
			process.stdout.write("\n Given Sum : " + sum);
			if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
			{
				process.stdout.write("\n None \n");
			}
			else
			{
				console.log("\n Element : " + dp[n][sum]);
			}
		}
	}
}

function main()
{
	var task = new Counting();
	// Define array of positive integers
	var arr = [4, 6, 2, 8, 5];
	var n = arr.length;
	// 31 = 8 + 8 + 8 + 5 + 2
	task.countElements(arr, n, 31);
	// 17 = 6 + 6 + 5
	task.countElements(arr, n, 17);
	task.countElements(arr, n, 3);
}
main();

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

#    Python 3 Program
#    Count the minimum number of elements required to given sum
class Counting :
	#  Returns the minimum value of two numbers
	def minimum(self, a, b) :
		if (a < b) :
			return a
		else :
			return b
		
	
	#  Handles the request of count minimum elements 
	#  Sum of list elements which is equal to given sum
	def countElements(self, arr, n, sum) :
		if (sum > 0) :
			dp = [[0] * (sum + 1) for _ in range(n + 1) ]
			i = 0
			j = 0
			element = 0
			#  Set default value
			i = 0
			while (i <= n) :
				j = 0
				while (j <= sum) :
					if (i == 0) :
						#  Set first row elements
						dp[i][j] = sum + 1
					else :
						dp[i][j] = 0
					
					j += 1
				
				i += 1
			i = 1
			#  Calculate result
			#  Execute loop through by list size
			while (i <= n) :
				#  Get element
				element = arr[i - 1]
				if (element > 0) :
					j = 1
					while (j <= sum) :
						if (element > j) :
							#  When list element is greater than given sum
							dp[i][j] = dp[i - 1][j]
						else :
							#  When list elements less than given sum
							dp[i][j] = self.minimum(dp[i - 1][j], 
                                                    dp[i][j - element] + 1)
						
						j += 1
					
				
				i += 1
			
			#  Display given sum
			print("\n Given Sum : ", sum, end = "")
			if (dp[n][sum] == sum + 1 or dp[n][sum] == 0) :
				print("\n None ")
			else :
				print("\n Element : ", dp[n][sum])
			
		
	

def main() :
	task = Counting()
	arr = [4, 6, 2, 8, 5]
	n = len(arr)
	#  31 = 8 + 8 + 8 + 5 + 2
	task.countElements(arr, n, 31)
	#  17 = 6 + 6 + 5
	task.countElements(arr, n, 17)
	task.countElements(arr, n, 3)

if __name__ == "__main__": main()

 Given Sum :  31
 Element :  5

 Given Sum :  17
 Element :  3

 Given Sum :  3
 None

#    Ruby Program
#    Count the minimum number of elements required to given sum
class Counting 
	#  Returns the minimum value of two numbers
	def minimum(a, b) 
		if (a < b) 
			return a
		else 
			return b
		end

	end

	#  Handles the request of count minimum elements 
	#  Sum of array elements which is equal to given sum
	def countElements(arr, n, sum) 
		if (sum > 0) 
			#  Auxiliary space
			dp = Array.new(n + 1) {Array.new(sum + 1) {0}}
			#  Loop controlling variables
			i = 0
			j = 0
			element = 0
			#  Set default value
			i = 0
			while (i <= n) 
				j = 0
				while (j <= sum) 
					if (i == 0) 
						#  Set first row elements
						dp[i][j] = sum + 1
					else 
						dp[i][j] = 0
					end

					j += 1
				end

				i += 1
			end

			#  Calculate result
			#  Execute loop through by array size
			i = 1
			while (i <= n) 
				#  Get element
				element = arr[i - 1]
				if (element > 0) 
					j = 1
					while (j <= sum) 
						if (element > j) 
							#  When array element is greater than given sum
							dp[i][j] = dp[i - 1][j]
						else 
							#  When array elements less than given sum
							dp[i][j] = self.minimum(dp[i - 1][j], 
                                                    dp[i][j - element] + 1)
						end

						j += 1
					end

				end

				i += 1
			end

			#  Display given sum
			print("\n Given Sum : ", sum)
			if (dp[n][sum] == sum + 1 || dp[n][sum] == 0) 
				print("\n None \n")
			else 
				print("\n Element : ", dp[n][sum], "\n")
			end

		end

	end

end

def main() 
	task = Counting.new()
	#  Define array of positive integers
	arr = [4, 6, 2, 8, 5]
	n = arr.length
	#  31 = 8 + 8 + 8 + 5 + 2
	task.countElements(arr, n, 31)
	#  17 = 6 + 6 + 5
	task.countElements(arr, n, 17)
	task.countElements(arr, n, 3)
end

main()

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None 

/*
    Scala Program
    Count the minimum number of elements required to given sum
*/
class Counting()
{
	// Returns the minimum value of two numbers
	def minimum(a: Int, b: Int): Int = {
		if (a < b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	def countElements(arr: Array[Int], n: Int, sum: Int): Unit = {
		if (sum > 0)
		{
			// Auxiliary space
			var dp: Array[Array[Int]] = Array.fill[Int](n + 1, sum + 1)(0);
			// Loop controlling variables
			var i: Int = 0;
			var j: Int = 0;
			var element: Int = 0;
			// Set default value
			i = 0;
			while (i <= n)
			{
				j = 0;
				while (j <= sum)
				{
					if (i == 0)
					{
						// Set first row elements
						dp(i)(j) = sum + 1;
					}
					else
					{
						dp(i)(j) = 0;
					}
					j += 1;
				}
				i += 1;
			}
			// Calculate result
			// Execute loop through by array size
			i = 1;
			while (i <= n)
			{
				// Get element
				element = arr(i - 1);
				if (element > 0)
				{
					j = 1;
					while (j <= sum)
					{
						if (element > j)
						{
							// When array element is greater than given sum
							dp(i)(j) = dp(i - 1)(j);
						}
						else
						{
							// When array elements less than given sum
							dp(i)(j) = minimum(dp(i - 1)(j), dp(i)(j - element) + 1);
						}
						j += 1;
					}
				}
				i += 1;
			}
			// Display given sum
			print("\n Given Sum : " + sum);
			if (dp(n)(sum) == sum + 1 || dp(n)(sum) == 0)
			{
				print("\n None \n");
			}
			else
			{
				println("\n Element : " + dp(n)(sum));
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Counting = new Counting();
		// Define array of positive integers
		var arr: Array[Int] = Array(4, 6, 2, 8, 5);
		var n: Int = arr.length;
		// 31 = 8 + 8 + 8 + 5 + 2
		task.countElements(arr, n, 31);
		// 17 = 6 + 6 + 5
		task.countElements(arr, n, 17);
		task.countElements(arr, n, 3);
	}
}

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

/*
    Swift 4 Program
    Count the minimum number of elements required to given sum
*/
class Counting
{
	// Returns the minimum value of two numbers
	func minimum(_ a: Int, _ b: Int)->Int
	{
		if (a < b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	func countElements(_ arr: [Int], _ n: Int, _ sum: Int)
	{
		if (sum > 0)
		{
			// Auxiliary space
			var dp: [[Int]] = Array(repeating: Array(repeating: 0, 
                                    count: sum + 1), count: n + 1);
			// Loop controlling variables
			var i: Int = 0;
			var j: Int = 0;
			var element: Int = 0;
			// Set default value
			i = 0;
			while (i <= n)
			{
				j = 0;
				while (j <= sum)
				{
					if (i == 0)
					{
						// Set first row elements
						dp[i][j] = sum + 1;
					}
					else
					{
						dp[i][j] = 0;
					}
					j += 1;
				}
				i += 1;
			}
			// Calculate result
			// Execute loop through by array size
			i = 1;
			while (i <= n)
			{
				// Get element
				element = arr[i - 1];
				if (element > 0)
				{
					j = 1;
					while (j <= sum)
					{
						if (element > j)
						{
							// When array element is greater than given sum
							dp[i][j] = dp[i - 1][j];
						}
						else
						{
							// When array elements less than given sum
							dp[i][j] = self.minimum(dp[i - 1][j], dp[i][j - element] + 1);
						}
						j += 1;
					}
				}
				i += 1;
			}
			// Display given sum
			print("\n Given Sum : ", sum, terminator: "");
			if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
			{
				print("\n None ");
			}
			else
			{
				print("\n Element : ", dp[n][sum]);
			}
		}
	}
}
func main()
{
	let task: Counting = Counting();
	// Define array of positive integers
	let arr: [Int] = [4, 6, 2, 8, 5];
	let n: Int = arr.count;
	// 31 = 8 + 8 + 8 + 5 + 2
	task.countElements(arr, n, 31);
	// 17 = 6 + 6 + 5
	task.countElements(arr, n, 17);
	task.countElements(arr, n, 3);
}
main();

 Given Sum :  31
 Element :  5

 Given Sum :  17
 Element :  3

 Given Sum :  3
 None

/*
    Kotlin Program
    Count the minimum number of elements required to given sum
*/
class Counting
{
	// Returns the minimum value of two numbers
	fun minimum(a: Int, b: Int): Int
	{
		if (a < b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Handles the request of count minimum elements 
	// Sum of array elements which is equal to given sum
	fun countElements(arr: Array < Int > , n: Int, sum: Int): Unit
	{
		if (sum > 0)
		{
			// Auxiliary space
			val dp: Array < Array < Int >> = Array(n + 1)
			{
				Array(sum + 1)
				{
					0
				}
			};
			// Loop controlling variables
			var i: Int = 0;
			var j: Int = 0;
			var element: Int ;
			// Set default value
			while (i <= n)
			{
				while (j <= sum)
				{
					if (i == 0)
					{
						// Set first row elements
						dp[i][j] = sum + 1;
					}
					else
					{
						dp[i][j] = 0;
					}
					j += 1;
				}
				i += 1;
              	j = 0;
			}
			// Calculate result
			// Execute loop through by array size
			i = 1;
			while (i <= n)
			{
				// Get element
				element = arr[i - 1];
				if (element > 0)
				{
					j = 1;
					while (j <= sum)
					{
						if (element > j)
						{
							// When array element is greater than given sum
							dp[i][j] = dp[i - 1][j];
						}
						else
						{
							// When array elements less than given sum
							dp[i][j] = this.minimum(dp[i - 1][j], 
                                                    dp[i][j - element] + 1);
						}
						j += 1;
					}
				}
				i += 1;
			}
			// Display given sum
			print("\n Given Sum : " + sum);
			if (dp[n][sum] == sum + 1 || dp[n][sum] == 0)
			{
				print("\n None \n");
			}
			else
			{
				println("\n Element : " + dp[n][sum]);
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Counting = Counting();
	// Define array of positive integers
	val arr: Array < Int > = arrayOf(4, 6, 2, 8, 5);
	val n: Int = arr.count();
	// 31 = 8 + 8 + 8 + 5 + 2
	task.countElements(arr, n, 31);
	// 17 = 6 + 6 + 5
	task.countElements(arr, n, 17);
	task.countElements(arr, n, 3);
}

 Given Sum : 31
 Element : 5

 Given Sum : 17
 Element : 3

 Given Sum : 3
 None

Resultant Output Explanation

We'll now explain the output of the provided code examples:

The first example uses a given sum of 31. From the provided array, we can obtain 31 using the elements [8, 8, 8, 5, 2]. The minimum number of elements required is 5.

In the second example, the given sum is 17. We can achieve this using the elements [6, 6, 5]. Thus, the minimum number of elements required is 3.

For the third example, the given sum is 3. There is no combination of elements from the array that can add up to 3. Hence, the result is "None."

Time Complexity

The time complexity of the provided algorithm is O(n * sum) since we have a nested loop iterating over n and sum elements. In the worst case, the algorithm will iterate over all elements and calculate the minimum for each sum. However, the space complexity is O(n * sum) as well due to the need for the auxiliary 2D array.

In conclusion, the algorithm efficiently solves the problem of counting the minimum number of elements required to achieve a given sum. It utilizes dynamic programming to find the optimal solution. By understanding the algorithm and analyzing the output, we can solve similar problems efficiently.