Posted on by Kalkicode
Code Backtracking

Find maximum size subset with given sum

In this article, we will discuss a problem where we need to find the maximum size subset with a given sum. We will provide an explanation of the problem statement, illustrate it with a suitable example, and then present an algorithm and pseudocode for solving the problem. Finally, we will explain the output obtained from the provided code, along with the time complexity of the solution.

Problem Statement

Given an array of integers and a target sum, we are tasked with finding the maximum size subset of the array that adds up to the given sum. We need to determine the elements of this subset and display them as output. If there are multiple subsets with the same maximum size, we can choose any one of them.

Example

Let's understand the problem with an example. Consider the following array of integers: 

	arr[] = {6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7}

We want to find the maximum size subset with a sum of 6.

Algorithm

To solve this problem, we can use a recursive approach. Here is the algorithm:

  1. Define a recursive function, longestSubset, which takes the following parameters:
    • The array of integers (collection)
    • An array to track the subset elements (track)
    • An array to store the output subset (output)
    • A pointer to the length of the subset (length)
    • The size of the array (n)
    • The target sum (k)
    • The current sum of the subset (sum)
    • The starting index for considering elements (start)
    • The current location in the subset (location)
  2. If the current length of the subset (length) is less than the current location (location) and the current sum (sum) is equal to the target sum (k), update the length and copy the track array to the output array.
  3. Iterate over the remaining elements of the array starting from the given start index:
    • Include the current element in the track array.
    • Recursively call the longestSubset function with an updated sum, start index, and location.
  4. In the main function, initialize the track and output arrays with zeros.
  5. Call the longestSubset function to find the maximum subset for the given target sum.
  6. If a subset is found (length > 0), display the output subset. Otherwise, display that the subset does not exist.

Pseudocode


function display(result[], n)
	for i = 0 to n-1
		print result[i]
	print new line

function longestSubset(collection[], track[], output[], length, n, k, sum, start, location)
	if length < location and sum == k
		length = location
		for x = 0 to location-1
			output[x] = track[x]
	for i = start to n-1
		track[location] = collection[i]
		longestSubset(collection, track, output, length, n, k, sum + collection[i], i + 1, location + 1)

function findSubsets(arr[], n, k)
	if n <= 0
		return
	track[n]
	output[n]
	length = 0
	for i = 0 to n-1
		output[i] = 0
		track[i] = 0
	longestSubset(arr, track, output, length, n, k, 0, 0, 0)
	if length > 0
		print "Longest subset of sum", k, "are"
		display(output, length)
	else
		print "Subset of sum", k, "does not exist"

arr[] = {6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7}
n = size of arr / size of arr[0]
k = 6
findSubsets(arr, n, k)
k = 45
findSubsets(arr, n, k)
k = 30
findSubsets(arr, n, k)

Code Solution

/*
   C Program for
   Find maximum size subset with given sum
*/
#include <stdio.h>

// Display subset value
void display(int result[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf(" %d", result[i]);
	}
	printf("\n");
}
// Finding the longest size subset with given sum
void longestSubset(int collection[], 
 int track[], int output[], 
 int *length, int n, int k, 
 int sum, int start, int location)
{
	if ( *length < location && sum == k)
	{
		// Get a new long subgroup with k sum
		*length = location;
		for (int x = 0; x < location; ++x)
		{
			// Get result sequence
			output[x] = track[x];
		}
	}
	for (int i = start; i < n; ++i)
	{
		// Collect value
		track[location] = collection[i];
		longestSubset(collection, track, output, length, n, k, sum + collection[i], i + 1, location + 1);
	}
}
// Handles the request to find subsets with given sum
void findSubsets(int arr[], int n, int k)
{
	if (n <= 0)
	{
		return;
	}
	// Used to tracking subset result
	int track[n];
	// Used to collect subset element
	int output[n];
	int length = 0;
	// Set default value
	for (int i = 0; i < n; ++i)
	{
		output[i] = 0;
		track[i] = 0;
	}
	// Find maximum subset of k sum
	longestSubset(arr, track, output, & length, n, k, 0, 0, 0);
	if (length > 0)
	{
		printf("\n Longest subset of sum %d are \n", k);
		display(output, length);
	}
	else
	{
		printf("\n Subset of sum %d are not exist", k);
	}
}
int main()
{
	int arr[] = {
		6 , 9 , 2 , 4 , 6 , 8 , 10 , -3 , -2 , 1 , -7
	};
	// Get the size
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 6;
	findSubsets(arr, n, k);
  	k = 45;
	findSubsets(arr, n, k);
  
    k = 30;
	findSubsets(arr, n, k);
	return 0;
}

Output

 Longest subset of sum 6 are
 6 9 2 -3 -2 1 -7

 Longest subset of sum 45 are
 6 9 2 4 6 8 10

 Longest subset of sum 30 are
 6 9 2 6 8 10 -3 -2 1 -7
/*
    Java Program for
    Find maximum size subset with given sum
*/
public class SubSetSum
{
	public int length;
	public SubSetSum()
	{
		this.length = 0;
	}
	// Display subset value
	public void display(int[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print("  " + result[i]);
		}
		System.out.print("\n");
	}
	// Finding the longest size subset with given sum
	public void longestSubset(int[] collection, int[] track, int[] output, int n, int k, int sum, int start, int location)
	{
		if (this.length < location && sum == k)
		{
			// Get a new long subgroup with k sum
			this.length = location;
			for (int x = 0; x < location; ++x)
			{
				// Get result sequence
				output[x] = track[x];
			}
		}
		for (int i = start; i < n; ++i)
		{
			// Collect value
			track[location] = collection[i];
			longestSubset(collection, track, output, n, k, sum + collection[i], i + 1, location + 1);
		}
	}
	// Handles the request to find subsets with given sum
	public void findSubsets(int[] arr, int n, int k)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		int[] track = new int[n];
		// Used to collect subset element
		int[] output = new int[n];
		this.length = 0;
		// Set default value
		for (int i = 0; i < n; ++i)
		{
			output[i] = 0;
			track[i] = 0;
		}
		// Find maximum subset of k sum
		longestSubset(arr, track, output, n, k, 0, 0, 0);
		if (this.length > 0)
		{
			System.out.print("\n Longest subset of sum " + k + " are \n");
			display(output, this.length);
		}
		else
		{
			System.out.print("\n Subset of sum " + k + " are not exist");
		}
	}
	public static void main(String[] args)
	{
		SubSetSum task = new SubSetSum();
		int[] arr = {
			6 , 9 , 2 , 4 , 6 , 8 , 10 , -3 , -2 , 1 , -7
		};
		// Get the size
		int n = arr.length;
		int k = 6;
		task.findSubsets(arr, n, k);
		k = 45;
		task.findSubsets(arr, n, k);
		k = 30;
		task.findSubsets(arr, n, k);
	}
}

Output

 Longest subset of sum 6 are
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are
  6  9  2  4  6  8  10

 Longest subset of sum 30 are
  6  9  2  6  8  10  -3  -2  1  -7
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program for
    Find maximum size subset with given sum
*/
class SubSetSum
{
	public: int length;
	SubSetSum()
	{
		this->length = 0;
	}
	// Display subset value
	void display(int result[], int n)
	{
		for (int i = 0; i < n; ++i)
		{
			cout << "  " << result[i];
		}
		cout << "\n";
	}
	// Finding the longest size subset with given sum
	void longestSubset(int collection[], int track[], int output[], int n, int k, int sum, int start, int location)
	{
		if (this->length < location && sum == k)
		{
			// Get a new long subgroup with k sum
			this->length = location;
          
			for (int x = 0; x < location; ++x)
			{
				// Get result sequence
				output[x] = track[x];
			}
		}
		for (int i = start; i < n; ++i)
		{
			// Collect value
			track[location] = collection[i];
			this->longestSubset(collection, track, output, n, k, sum + collection[i], i + 1, location + 1);
		}
	}
	// Handles the request to find subsets with given sum
	void findSubsets(int arr[], int n, int k)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		int track[n];
		// Used to collect subset element
		int output[n];
		this->length = 0;
		// Set default value
		for (int i = 0; i < n; ++i)
		{
			output[i] = 0;
			track[i] = 0;
		}
		// Find maximum subset of k sum
		this->longestSubset(arr, track, output, n, k, 0, 0, 0);
		if (this->length > 0)
		{
			cout << "\n Longest subset of sum " << k << " are \n";
			this->display(output, this->length);
		}
		else
		{
			cout << "\n Subset of sum " << k << " are not exist";
		}
	}
};
int main()
{
	SubSetSum task = SubSetSum();
	int arr[] = {
		6 , 9 , 2 , 4 , 6 , 8 , 10 , -3 , -2 , 1 , -7
	};
	// Get the size
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 6;
	task.findSubsets(arr, n, k);
	k = 45;
	task.findSubsets(arr, n, k);
	k = 30;
	task.findSubsets(arr, n, k);
	return 0;
}

Output

 Longest subset of sum 6 are
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are
  6  9  2  4  6  8  10

 Longest subset of sum 30 are
  6  9  2  6  8  10  -3  -2  1  -7
// Include namespace system
using System;
/*
    C# Program for
    Find maximum size subset with given sum
*/
public class SubSetSum
{
	public int length;
	public SubSetSum()
	{
		this.length = 0;
	}
	// Display subset value
	public void display(int[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write("  " + result[i]);
		}
		Console.Write("\n");
	}
	// Finding the longest size subset with given sum
	public void longestSubset(int[] collection, int[] track, int[] output, int n, int k, int sum, int start, int location)
	{
		if (this.length < location && sum == k)
		{
			// Get a new long subgroup with k sum
			this.length = location;
			for (int x = 0; x < location; ++x)
			{
				// Get result sequence
				output[x] = track[x];
			}
		}
		for (int i = start; i < n; ++i)
		{
			// Collect value
			track[location] = collection[i];
			longestSubset(collection, track, output, n, k, sum + collection[i], i + 1, location + 1);
		}
	}
	// Handles the request to find subsets with given sum
	public void findSubsets(int[] arr, int n, int k)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		int[] track = new int[n];
		// Used to collect subset element
		int[] output = new int[n];
		this.length = 0;
		// Set default value
		for (int i = 0; i < n; ++i)
		{
			output[i] = 0;
			track[i] = 0;
		}
		// Find maximum subset of k sum
		longestSubset(arr, track, output, n, k, 0, 0, 0);
		if (this.length > 0)
		{
			Console.Write("\n Longest subset of sum " + k + " are \n");
			display(output, this.length);
		}
		else
		{
			Console.Write("\n Subset of sum " + k + " are not exist");
		}
	}
	public static void Main(String[] args)
	{
		SubSetSum task = new SubSetSum();
		int[] arr = {
			6 , 9 , 2 , 4 , 6 , 8 , 10 , -3 , -2 , 1 , -7
		};
		// Get the size
		int n = arr.Length;
		int k = 6;
		task.findSubsets(arr, n, k);
		k = 45;
		task.findSubsets(arr, n, k);
		k = 30;
		task.findSubsets(arr, n, k);
	}
}

Output

 Longest subset of sum 6 are
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are
  6  9  2  4  6  8  10

 Longest subset of sum 30 are
  6  9  2  6  8  10  -3  -2  1  -7
<?php
/*
    Php Program for
    Find maximum size subset with given sum
*/
class SubSetSum
{
	public $length;

	function __construct()
	{
		$this->length = 0;
	}
	// Display subset value
	public	function display( & $result, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo "  ". $result[$i];
		}
		echo "\n";
	}
	// Finding the longest size subset with given sum
	public	function longestSubset( & $collection, & $track, & $output, $n, $k, $sum, $start, $location)
	{
		if ($this->length < $location && $sum == $k)
		{
			// Get a new long subgroup with k sum
			$this->length = $location;
			for ($x = 0; $x < $location; ++$x)
			{
				// Get result sequence
				$output[$x] = $track[$x];
			}
		}
		for ($i = $start; $i < $n; ++$i)
		{
			// Collect value
			$track[$location] = $collection[$i];
			$this->longestSubset($collection, $track, $output, $n, $k, $sum + $collection[$i], $i + 1, $location + 1);
		}
	}
	// Handles the request to find subsets with given sum
	public	function findSubsets( & $arr, $n, $k)
	{
		if ($n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		$track = array_fill(0, $n, 0);
		// Used to collect subset element
		$output = array_fill(0, $n, 0);
		$this->length = 0;
		// Find maximum subset of k sum
		$this->longestSubset($arr, $track, $output, $n, $k, 0, 0, 0);
		if ($this->length > 0)
		{
			echo "\n Longest subset of sum ". $k ." are \n";
			$this->display($output, $this->length);
		}
		else
		{
			echo "\n Subset of sum ". $k ." are not exist";
		}
	}
}

function main()
{
	$task = new SubSetSum();
	$arr = array(6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7);
	// Get the size
	$n = count($arr);
	$k = 6;
	$task->findSubsets($arr, $n, $k);
	$k = 45;
	$task->findSubsets($arr, $n, $k);
	$k = 30;
	$task->findSubsets($arr, $n, $k);
}
main();

Output

 Longest subset of sum 6 are
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are
  6  9  2  4  6  8  10

 Longest subset of sum 30 are
  6  9  2  6  8  10  -3  -2  1  -7
/*
    Node Js Program for
    Find maximum size subset with given sum
*/
class SubSetSum
{
	constructor()
	{
		this.length = 0;
	}
	// Display subset value
	display(result, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write("  " + result[i]);
		}
		process.stdout.write("\n");
	}
	// Finding the longest size subset with given sum
	longestSubset(collection, track, output, n, k, sum, start, location)
	{
		if (this.length < location && sum == k)
		{
			// Get a new long subgroup with k sum
			this.length = location;
			for (var x = 0; x < location; ++x)
			{
				// Get result sequence
				output[x] = track[x];
			}
		}
		for (var i = start; i < n; ++i)
		{
			// Collect value
			track[location] = collection[i];
			this.longestSubset(collection, track, output, n, k, sum + collection[i], i + 1, location + 1);
		}
	}
	// Handles the request to find subsets with given sum
	findSubsets(arr, n, k)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		var track = Array(n).fill(0);
		// Used to collect subset element
		var output = Array(n).fill(0);
		this.length = 0;
		// Find maximum subset of k sum
		this.longestSubset(arr, track, output, n, k, 0, 0, 0);
		if (this.length > 0)
		{
			process.stdout.write("\n Longest subset of sum " + k + " are \n");
			this.display(output, this.length);
		}
		else
		{
			process.stdout.write("\n Subset of sum " + k + " are not exist");
		}
	}
}

function main()
{
	var task = new SubSetSum();
	var arr = [6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7];
	// Get the size
	var n = arr.length;
	var k = 6;
	task.findSubsets(arr, n, k);
	k = 45;
	task.findSubsets(arr, n, k);
	k = 30;
	task.findSubsets(arr, n, k);
}
main();

Output

 Longest subset of sum 6 are
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are
  6  9  2  4  6  8  10

 Longest subset of sum 30 are
  6  9  2  6  8  10  -3  -2  1  -7
#   Python 3 Program for
#   Find maximum size subset with given sum

class SubSetSum :
	
	def __init__(self) :
		self.length = 0
	
	#  Display subset value
	def display(self, result, n) :
		i = 0
		while (i < n) :
			print("  ", result[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Finding the longest size subset with given sum
	def longestSubset(self, collection, track, output, n, k, sum, start, location) :
		if (self.length < location and sum == k) :
			#  Get a new long subgroup with k sum
			self.length = location
			x = 0
			while (x < location) :
				#  Get result sequence
				output[x] = track[x]
				x += 1
			
		
		i = start
		while (i < n) :
			#  Collect value
			track[location] = collection[i]
			self.longestSubset(collection, track, output, n, k, sum + collection[i], i + 1, location + 1)
			i += 1
		
	
	#  Handles the request to find subsets with given sum
	def findSubsets(self, arr, n, k) :
		if (n <= 0) :
			return
		
		#  Used to tracking subset result
		track = [0] * (n)
		#  Used to collect subset element
		output = [0] * (n)
		self.length = 0
		#  Find maximum subset of k sum
		self.longestSubset(arr, track, output, n, k, 0, 0, 0)
		if (self.length > 0) :
			print("\n Longest subset of sum ", k ," are ")
			self.display(output, self.length)
		else :
			print("\n Subset of sum ", k ," are not exist", end = "")
		
	

def main() :
	task = SubSetSum()
	arr = [6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7]
	#  Get the size
	n = len(arr)
	k = 6
	task.findSubsets(arr, n, k)
	k = 45
	task.findSubsets(arr, n, k)
	k = 30
	task.findSubsets(arr, n, k)

if __name__ == "__main__": main()

Output

 Longest subset of sum  6  are
   6   9   2   -3   -2   1   -7

 Longest subset of sum  45  are
   6   9   2   4   6   8   10

 Longest subset of sum  30  are
   6   9   2   6   8   10   -3   -2   1   -7
#  Ruby Program for
#  Find maximum size subset with given sum

class SubSetSum  
	# Define the accessor and reader of class SubSetSum  
	attr_reader :length
	attr_accessor :length
 
	
	def initialize() 
		self.length = 0
	end

	#  Display subset value
	def display(result, n) 
		i = 0
		while (i < n) 
			print("  ", result[i])
			i += 1
		end

		print("\n")
	end

	#  Finding the longest size subset with given sum
	def longestSubset(collection, track, output, n, k, sum, start, location) 
		if (self.length < location && sum == k) 
			#  Get a new long subgroup with k sum
			self.length = location
			x = 0
			while (x < location) 
				#  Get result sequence
				output[x] = track[x]
				x += 1
			end

		end

		i = start
		while (i < n) 
			#  Collect value
			track[location] = collection[i]
			self.longestSubset(collection, track, output, n, k, sum + collection[i], i + 1, location + 1)
			i += 1
		end

	end

	#  Handles the request to find subsets with given sum
	def findSubsets(arr, n, k) 
		if (n <= 0) 
			return
		end

		#  Used to tracking subset result
		track = Array.new(n) {0}
		#  Used to collect subset element
		output = Array.new(n) {0}
		self.length = 0
		#  Find maximum subset of k sum
		self.longestSubset(arr, track, output, n, k, 0, 0, 0)
		if (self.length > 0) 
			print("\n Longest subset of sum ", k ," are \n")
			self.display(output, self.length)
		else 
			print("\n Subset of sum ", k ," are not exist")
		end

	end

end

def main() 
	task = SubSetSum.new()
	arr = [6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7]
	#  Get the size
	n = arr.length
	k = 6
	task.findSubsets(arr, n, k)
	k = 45
	task.findSubsets(arr, n, k)
	k = 30
	task.findSubsets(arr, n, k)
end

main()

Output

 Longest subset of sum 6 are 
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are 
  6  9  2  4  6  8  10

 Longest subset of sum 30 are 
  6  9  2  6  8  10  -3  -2  1  -7

/*
    Scala Program for
    Find maximum size subset with given sum
*/
class SubSetSum(var length: Int)
{
	def this()
	{
		this(0);
	}
	// Display subset value
	def display(result: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print("  " + result(i));
			i += 1;
		}
		print("\n");
	}
	// Finding the longest size subset with given sum
	def longestSubset(collection: Array[Int], 
      track: Array[Int], output: Array[Int], 
      n: Int, k: Int, sum: Int, start: Int, location: Int): Unit = {
		if (this.length < location && sum == k)
		{
			// Get a new long subgroup with k sum
			this.length = location;
			var x: Int = 0;
			while (x < location)
			{
				// Get result sequence
				output(x) = track(x);
				x += 1;
			}
		}
		var i: Int = start;
		while (i < n)
		{
			// Collect value
			track(location) = collection(i);
			this.longestSubset(collection, track, output, n, k, sum + collection(i), i + 1, location + 1);
			i += 1;
		}
	}
	// Handles the request to find subsets with given sum
	def findSubsets(arr: Array[Int], n: Int, k: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		var track: Array[Int] = Array.fill[Int](n)(0);
		// Used to collect subset element
		var output: Array[Int] = Array.fill[Int](n)(0);
		this.length = 0;
		// Find maximum subset of k sum
		this.longestSubset(arr, track, output, n, k, 0, 0, 0);
		if (this.length > 0)
		{
			print("\n Longest subset of sum " + k + " are \n");
			this.display(output, this.length);
		}
		else
		{
			print("\n Subset of sum " + k + " are not exist");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SubSetSum = new SubSetSum();
		var arr: Array[Int] = Array(6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7);
		// Get the size
		var n: Int = arr.length;
		var k: Int = 6;
		task.findSubsets(arr, n, k);
		k = 45;
		task.findSubsets(arr, n, k);
		k = 30;
		task.findSubsets(arr, n, k);
	}
}

Output

 Longest subset of sum 6 are
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are
  6  9  2  4  6  8  10

 Longest subset of sum 30 are
  6  9  2  6  8  10  -3  -2  1  -7
/*
    Swift 4 Program for
    Find maximum size subset with given sum
*/
class SubSetSum
{
	var length: Int;
	init()
	{
		self.length = 0;
	}
	// Display subset value
	func display(_ result: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  ", result[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Finding the longest size subset with given sum
	func longestSubset(_ collection: [Int], _ track: inout[Int], _ output: inout[Int], _ n: Int, _ k: Int, _ sum: Int, _ start: Int, _ location: Int)
	{
		if (self.length < location && sum == k)
		{
			// Get a new long subgroup with k sum
			self.length = location;
			var x: Int = 0;
			while (x < location)
			{
				// Get result sequence
				output[x] = track[x];
				x += 1;
			}
		}
		var i: Int = start;
		while (i < n)
		{
			// Collect value
			track[location] = collection[i];
			self.longestSubset(collection, &track, &output, n, k, sum + collection[i], i + 1, location + 1);
			i += 1;
		}
	}
	// Handles the request to find subsets with given sum
	func findSubsets(_ arr: [Int], _ n: Int, _ k: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		var track: [Int] = Array(repeating: 0, count: n);
		// Used to collect subset element
		var output: [Int] = Array(repeating: 0, count: n);
		self.length = 0;
		// Find maximum subset of k sum
		self.longestSubset(arr, &track, &output, n, k, 0, 0, 0);
		if (self.length > 0)
		{
			print("\n Longest subset of sum ", k ," are ");
			self.display(output, self.length);
		}
		else
		{
			print("\n Subset of sum ", k ," are not exist", terminator: "");
		}
	}
}
func main()
{
	let task: SubSetSum = SubSetSum();
	let arr: [Int] = [6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7];
	// Get the size
	let n: Int = arr.count;
	var k: Int = 6;
	task.findSubsets(arr, n, k);
	k = 45;
	task.findSubsets(arr, n, k);
	k = 30;
	task.findSubsets(arr, n, k);
}
main();

Output

 Longest subset of sum  6  are
   6   9   2   -3   -2   1   -7

 Longest subset of sum  45  are
   6   9   2   4   6   8   10

 Longest subset of sum  30  are
   6   9   2   6   8   10   -3   -2   1   -7
/*
    Kotlin Program for
    Find maximum size subset with given sum
*/
class SubSetSum
{
	var length: Int;
	constructor()
	{
		this.length = 0;
	}
	// Display subset value
	fun display(result: Array<Int> , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  " + result[i]);
			i += 1;
		}
		print("\n");
	}
	// Finding the longest size subset with given sum
	fun longestSubset(collection: Array<Int> , track: Array<Int> , output: Array<Int> , n: Int, k: Int, sum: Int, start: Int, location: Int): Unit
	{
		if (this.length < location && sum == k)
		{
			// Get a new long subgroup with k sum
			this.length = location;
			var x: Int = 0;
			while (x < location)
			{
				// Get result sequence
				output[x] = track[x];
				x += 1;
			}
		}
		var i: Int = start;
		while (i < n)
		{
			// Collect value
			track[location] = collection[i];
			this.longestSubset(collection, track, output, n, k, sum + collection[i], i + 1, location + 1);
			i += 1;
		}
	}
	// Handles the request to find subsets with given sum
	fun findSubsets(arr: Array<Int> , n: Int, k: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// Used to tracking subset result
		var track: Array <Int> = Array(n)
		{
			0
		};
		// Used to collect subset element
		var output: Array<Int> = Array(n)
		{
			0
		};
		this.length = 0;
		// Find maximum subset of k sum
		this.longestSubset(arr, track, output, n, k, 0, 0, 0);
		if (this.length > 0)
		{
			print("\n Longest subset of sum " + k + " are \n");
			this.display(output, this.length);
		}
		else
		{
			print("\n Subset of sum " + k + " are not exist");
		}
	}
}
fun main(args: Array <String> ): Unit
{
	var task: SubSetSum = SubSetSum();
	var arr: Array<Int> = arrayOf(6, 9, 2, 4, 6, 8, 10, -3, -2, 1, -7);
	// Get the size
	var n: Int = arr.count();
	var k: Int = 6;
	task.findSubsets(arr, n, k);
	k = 45;
	task.findSubsets(arr, n, k);
	k = 30;
	task.findSubsets(arr, n, k);
}

Output

 Longest subset of sum 6 are
  6  9  2  -3  -2  1  -7

 Longest subset of sum 45 are
  6  9  2  4  6  8  10

 Longest subset of sum 30 are
  6  9  2  6  8  10  -3  -2  1  -7

Output Explanation

The provided code produces the following output: 

Longest subset of sum 6 are
6 9 2 -3 -2 1 -7

Longest subset of sum 45 are
6 9 2 4 6 8 10

Longest subset of sum 30 are
6 9 2 6 8 10 -3 -2 1 -7

The output shows the longest subsets with the given sums. For example, for a sum of 6, the longest subset is [6, 9, 2, -3, -2, 1, -7]. Similarly, for a sum of 45, the longest subset is [6, 9, 2, 4, 6, 8, 10]. Finally, for a sum of 30, the longest subset is [6, 9, 2, 6, 8, 10, -3, -2, 1, -7].

Time Complexity

The time complexity of the provided solution is determined by the number of recursive calls and the operations within each call. Since we are exploring all possible subsets, the time complexity is exponential.

The overall time complexity of the code is O(2^n), where n is the size of the input array. This is because, for each element, we have two choices: include it or exclude it in the subset. As a result, the number of recursive calls grows exponentially with the size of the input array.

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





Categories
Relative Post