Find maximum size subset with given sum
Here given code implementation process.
/*
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
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