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:
- 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)
- 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.
- 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.
- In the main function, initialize the track and output arrays with zeros.
- Call the longestSubset function to find the maximum subset for the given target sum.
- 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.
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