Find longest length subsequence of given sum
The problem Find longest length subsequence of given sum involves finding the longest subsequence of a given array such that the sum of its elements is equal to a given target sum. The subsequence can contain any elements from the original array, but their order should be preserved. The goal is to find and display the longest subsequence with the specified sum, if it exists.
Problem Statement
Given an array of integers and a target sum, we need to find and print the longest subsequence with the given sum.
Example
Let's consider the following input array and target sum:
Array: [5, 7, 2, 3, 4, 9, 1, -4, 10]
Sum: 10
The output will be as follows:
Longest subsequences of sum 10 are: [5, 2, 3, 4, -4]
Idea to Solve the Problem
To find the longest subsequence with the given sum, we can use a recursive approach along with a stack data structure. The idea is to consider each element in the array and decide whether to include it in the current subsequence or not. For each element, we have two choices: include it or exclude it.
Algorithm
- Create a stack data structure to hold the elements of the current subsequence.
- Traverse the array from the last element to the first element.
- For each element at index
i
in the array: a. Call the recursive functionsum_subsequence
with the array, an output array, the indexi-1
, the target sum, and the current sum (k
) set to 0. b. Push the element at indexi
into the stack. c. If the current sum (k
) is equal to the target sum, check if the length of the stack is greater than the current result. If yes, update the result with the length of the stack and copy the elements from the stack to the output array. d. Call the recursive functionsum_subsequence
with the array, the output array, the indexi-1
, the target sum, and the updated current sum (k + collection[i]
). e. Pop the element from the stack. - In the main function, call the
subsequences
function with the array, its size, and the target sum.
Pseudocode
Function sum_subsequence(collection, output, location, sum, k):
if location is -1:
return
else:
Call sum_subsequence(collection, output, location - 1, sum, k)
Push collection[location] into the stack
If k is equal to sum:
If length of stack is greater than result:
Update result with length of stack
Copy elements from stack to output array
Call sum_subsequence(collection, output, location - 1, sum, k + collection[location])
Pop an element from the stack
Code Solution
Here given code implementation process.
// C program
// Find longest length subsequence of given sum
#include <stdio.h>
#include <stdlib.h>
struct MyStack
{
int element;
struct MyStack *next;
};
//Add node at top of stack
void push(struct MyStack**top,int data)
{
//Make a new node
struct MyStack *new_node = (struct MyStack * ) malloc(sizeof(struct MyStack));
if (new_node != NULL)
{
//Set node values
new_node->element = data;
new_node->next = *top;
*top = new_node;
}
else
{
printf("Memory Overflow\n");
}
}
// Remove top element
void pop(struct MyStack**top)
{
if(*top != NULL)
{
struct MyStack*temp = *top;
*top = temp->next;
free(temp);
temp = NULL;
}
}
// Print collection elements
void display(int collection[],int size)
{
for (int i = 0; i < size; ++i)
{
printf(" %d ",collection[i]);
}
printf("\n");
}
//Check whether the stack contains more elements than the previous result
int is_new_result(struct MyStack*top,int length)
{
struct MyStack*temp = top;
int counter = 0;
//Count the stack element until it's less than previous result
while(temp != NULL && counter <= length )
{
counter++;
temp = temp->next;
}
if(counter > length)
{
// When we get new result
return 1;
}
else
{
return 0;
}
}
//Find Longest subsequence of given sum
void sum_subsequence(int collection[],struct MyStack**top,int output[], int *capacity,int location,int sum,int k)
{
if(location==-1)
{
return;
}
else
{
sum_subsequence(collection,top,output,capacity,location-1,sum,k);
//Add element into stack
push(top,collection[location]);
if(sum == k + collection[location])
{
// When subsequence sum is equal to given sum
if(*top != NULL)
{
if(is_new_result(*top,*capacity) == 1)
{
// Get new solution
int length = 0;
struct MyStack *temp = *top;
// Collects new solution
while(temp != NULL)
{
output[length] = temp->element;
temp = temp->next;
length++;
}
// Update new length
*capacity = length;
}
}
}
sum_subsequence(collection,top,output,capacity,location-1,sum,k + collection[location]);
//Remove a top element
pop(top);
}
}
// Handles the request to find longest length sum
void subsequences(int collection[],int size,int sum)
{
if(size <= 0 )
{
return;
}
struct MyStack*top = NULL;
int output[size];
int capacity = 0;
printf("\n Given collection \n");
display(collection,size);
sum_subsequence(collection,&top,output,&capacity,size-1,sum,0);
if(capacity > 0)
{
printf("\n Longest subsequences of sum %d are \n",sum);
display(output,capacity);
}
else
{
printf("\n Subsequences of sum %d are not exist \n",sum);
}
}
int main()
{
int arr[] = { 5, 7 , 2, 3, 4 , 9, 1, -4,10};
//Get the size
int size = sizeof(arr)/sizeof(arr[0]);
int sum = 10;
// [ 5 2 3 4 -4 ]
// or
// [ 7 2 4 1 -4 ]
subsequences(arr,size,sum);
return 0;
}
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
/*
Java program
Find longest length subsequence of given sum
*/
//Stack Node
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public Node top;
public int length;
public MyStack()
{
this.top = null;
this.length = 0;
}
//Add a new element in stack
public void push(int data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length++;
}
else
{
System.out.print("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
this.length--;
}
}
//check that whether stack is empty or not
public boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
public int is_size()
{
return this.length;
}
//Used to get top element of stack
public int peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
public MyStack stack;
public int result;
public Subsequence()
{
stack = new MyStack();
this.result = 0;
}
// Display given array elements
public void display(int[] collection, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + collection[i] + " ");
}
}
//Find Longest subsequence of given sum
public void sum_subsequence(int[] collection, int[] output, int location, int sum, int k)
{
if (location == -1)
{
return;
}
else
{
sum_subsequence(collection, output, location - 1, sum, k);
//Add element into stack
this.stack.push(collection[location]);
if (sum == k + collection[location])
{
// When subsequence sum is equal to given sum
if (this.stack.is_empty() == false)
{
if (this.stack.length > this.result)
{
// Get new solution
int length = 0;
// Get top element of stack
Node temp = this.stack.top;
// Collects new solution
while (temp != null)
{
output[length] = temp.data;
//visit to next node
temp = temp.next;
length++;
}
// Update new length
this.result = this.stack.length;
}
}
}
sum_subsequence(collection, output, location - 1, sum, k + collection[location]);
//Remove a top element
this.stack.pop();
}
}
// Handles the request to find longest length sum
public void subsequences(int[] collection, int size, int sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
int[] output = new int[size];
this.result = 0;
// Display given collection elements
System.out.print("\n Given collection \n");
display(collection, size);
sum_subsequence(collection, output, size - 1, sum, 0);
if (this.result > 0)
{
System.out.print("\n Longest subsequences of sum " + sum + " are \n");
display(output, this.result);
}
else
{
System.out.print("\n Subsequences of sum " + sum + " are not exist \n");
}
}
public static void main(String[] args)
{
Subsequence obj = new Subsequence();
int[] collection = {
5 , 7 , 2 , 3 , 4 , 9 , 1 , -4 , 10
};
//Get the size
int size = collection.length;
obj.subsequences(collection, size,10);
}
}
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Find longest length subsequence of given sum
*/
//Stack Node
class Node
{
public:
int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
//Define custom stack and its operation
class MyStack
{
public: Node *top;
int length;
MyStack()
{
this->top = NULL;
this->length = 0;
}
//Add a new element in stack
void push(int data)
{
//Make a new stack node
Node *new_node = new Node(data);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
this->length++;
}
else
{
cout << "Memory overflow\n";
}
}
//remove a top element in stack
void pop()
{
if (this->top != NULL)
{
this->top = this->top->next;
this->length--;
}
}
//check that whether stack is empty or not
bool is_empty()
{
if (this->top != NULL)
{
return false;
}
else
{
return true;
}
}
int is_size()
{
return this->length;
}
//Used to get top element of stack
int peek()
{
if (this->top != NULL)
{
return this->top->data;
}
else
{
return 0;
}
}
};
class Subsequence
{
public: MyStack *stack;
int result;
Subsequence()
{
this->stack = new MyStack();
this->result = 0;
}
// Display given array elements
void display(int collection[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << collection[i] << " ";
}
}
//Find Longest subsequence of given sum
void sum_subsequence(int collection[], int output[], int location, int sum, int k)
{
if (location == -1)
{
return;
}
else
{
this->sum_subsequence(collection, output, location - 1, sum, k);
//Add element into stack
this->stack->push(collection[location]);
if (sum == k + collection[location])
{
// When subsequence sum is equal to given sum
if (this->stack->is_empty() == false)
{
if (this->stack->length > this->result)
{
// Get new solution
int length = 0;
// Get top element of stack
Node *temp = this->stack->top;
// Collects new solution
while (temp != NULL)
{
output[length] = temp->data;
//visit to next node
temp = temp->next;
length++;
}
// Update new length
this->result = this->stack->length;
}
}
}
this->sum_subsequence(collection, output, location - 1, sum, k + collection[location]);
//Remove a top element
this->stack->pop();
}
}
// Handles the request to find longest length sum
void subsequences(int collection[], int size, int sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
int output[size];
this->result = 0;
// Display given collection elements
cout << "\n Given collection \n";
this->display(collection, size);
this->sum_subsequence(collection, output, size - 1, sum, 0);
if (this->result > 0)
{
cout << "\n Longest subsequences of sum " << sum << " are \n";
this->display(output, this->result);
}
else
{
cout << "\n Subsequences of sum " << sum << " are not exist \n";
}
}
};
int main()
{
Subsequence obj = Subsequence();
int collection[] = {
5 , 7 , 2 , 3 , 4 , 9 , 1 , -4 , 10
};
//Get the size
int size = sizeof(collection) / sizeof(collection[0]);
// [ 5 2 3 4 -4 ]
// or
// [ 7 2 4 1 -4 ]
obj.subsequences(collection, size, 10);
return 0;
}
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
//Include namespace system
using System;
/*
C# program
Find longest length subsequence of given sum
*/
//Stack Node
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public Node top;
public int length;
public MyStack()
{
this.top = null;
this.length = 0;
}
//Add a new element in stack
public void push(int data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length++;
}
else
{
Console.Write("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
this.length--;
}
}
//check that whether stack is empty or not
public Boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
public int is_size()
{
return this.length;
}
//Used to get top element of stack
public int peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
public MyStack stack;
public int result;
public Subsequence()
{
stack = new MyStack();
this.result = 0;
}
// Display given array elements
public void display(int[] collection, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + collection[i] + " ");
}
}
//Find Longest subsequence of given sum
public void sum_subsequence(int[] collection, int[] output, int location, int sum, int k)
{
if (location == -1)
{
return;
}
else
{
sum_subsequence(collection, output, location - 1, sum, k);
//Add element into stack
this.stack.push(collection[location]);
if (sum == k + collection[location])
{
// When subsequence sum is equal to given sum
if (this.stack.is_empty() == false)
{
if (this.stack.length > this.result)
{
// Get new solution
int length = 0;
// Get top element of stack
Node temp = this.stack.top;
// Collects new solution
while (temp != null)
{
output[length] = temp.data;
//visit to next node
temp = temp.next;
length++;
}
// Update new length
this.result = this.stack.length;
}
}
}
sum_subsequence(collection, output, location - 1, sum, k + collection[location]);
//Remove a top element
this.stack.pop();
}
}
// Handles the request to find longest length sum
public void subsequences(int[] collection, int size, int sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
int[] output = new int[size];
this.result = 0;
// Display given collection elements
Console.Write("\n Given collection \n");
display(collection, size);
sum_subsequence(collection, output, size - 1, sum, 0);
if (this.result > 0)
{
Console.Write("\n Longest subsequences of sum " + sum + " are \n");
display(output, this.result);
}
else
{
Console.Write("\n Subsequences of sum " + sum + " are not exist \n");
}
}
public static void Main(String[] args)
{
Subsequence obj = new Subsequence();
int[] collection = {
5 , 7 , 2 , 3 , 4 , 9 , 1 , -4 , 10
};
//Get the size
int size = collection.Length;
// [ 5 2 3 4 -4 ]
// or
// [ 7 2 4 1 -4 ]
obj.subsequences(collection, size, 10);
}
}
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
<?php
/*
Php program
Find longest length subsequence of given sum
*/
//Stack Node
class Node
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public $top;
public $length;
function __construct()
{
$this->top = null;
$this->length = 0;
}
//Add a new element in stack
public function push($data)
{
//Make a new stack node
$new_node = new Node($data);
if ($new_node != null)
{
$new_node->next = $this->top;
$this->top = $new_node;
$this->length++;
}
else
{
echo "Memory overflow\n";
}
}
//remove a top element in stack
public function pop()
{
if ($this->top != null)
{
$this->top = $this->top->next;
$this->length--;
}
}
//check that whether stack is empty or not
public function is_empty()
{
if ($this->top != null)
{
return false;
}
else
{
return true;
}
}
public function is_size()
{
return $this->length;
}
//Used to get top element of stack
public function peek()
{
if ($this->top != null)
{
return $this->top->data;
}
else
{
return 0;
}
}
}
class Subsequence
{
public $stack;
public $result;
function __construct()
{
$this->stack = new MyStack();
$this->result = 0;
}
// Display given array elements
public function display( & $collection, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $collection[$i] ." ";
}
}
//Find Longest subsequence of given sum
public function sum_subsequence( & $collection, & $output, $location, $sum, $k)
{
if ($location == -1)
{
return;
}
else
{
$this->sum_subsequence($collection, $output, $location - 1, $sum, $k);
//Add element into stack
$this->stack->push($collection[$location]);
if ($sum == $k + $collection[$location])
{
// When subsequence sum is equal to given sum
if ($this->stack->is_empty() == false)
{
if ($this->stack->length > $this->result)
{
// Get new solution
$length = 0;
// Get top element of stack
$temp = $this->stack->top;
// Collects new solution
while ($temp != null)
{
$output[$length] = $temp->data;
//visit to next node
$temp = $temp->next;
$length++;
}
// Update new length
$this->result = $this->stack->length;
}
}
}
$this->sum_subsequence($collection, $output, $location - 1, $sum, $k + $collection[$location]);
//Remove a top element
$this->stack->pop();
}
}
// Handles the request to find longest length sum
public function subsequences( & $collection, $size, $sum)
{
if ($size <= 0)
{
return;
}
// Used to collect result
$output = array_fill(0, $size, 0);
$this->result = 0;
// Display given collection elements
echo "\n Given collection \n";
$this->display($collection, $size);
$this->sum_subsequence($collection, $output, $size - 1, $sum, 0);
if ($this->result > 0)
{
echo "\n Longest subsequences of sum ". $sum ." are \n";
$this->display($output, $this->result);
}
else
{
echo "\n Subsequences of sum ". $sum ." are not exist \n";
}
}
}
function main()
{
$obj = new Subsequence();
$collection = array(5, 7, 2, 3, 4, 9, 1, -4, 10);
//Get the size
$size = count($collection);
// [ 5 2 3 4 -4 ]
// or
// [ 7 2 4 1 -4 ]
$obj->subsequences($collection, $size, 10);
}
main();
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
/*
Node Js program
Find longest length subsequence of given sum
*/
//Stack Node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
constructor()
{
this.top = null;
this.length = 0;
}
//Add a new element in stack
push(data)
{
//Make a new stack node
var new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length++;
}
else
{
process.stdout.write("Memory overflow\n");
}
}
//remove a top element in stack
pop()
{
if (this.top != null)
{
this.top = this.top.next;
this.length--;
}
}
//check that whether stack is empty or not
is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
is_size()
{
return this.length;
}
//Used to get top element of stack
peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
constructor()
{
this.stack = new MyStack();
this.result = 0;
}
// Display given array elements
display(collection, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + collection[i] + " ");
}
}
//Find Longest subsequence of given sum
sum_subsequence(collection, output, location, sum, k)
{
if (location == -1)
{
return;
}
else
{
this.sum_subsequence(collection, output, location - 1, sum, k);
//Add element into stack
this.stack.push(collection[location]);
if (sum == k + collection[location])
{
// When subsequence sum is equal to given sum
if (this.stack.is_empty() == false)
{
if (this.stack.length > this.result)
{
// Get new solution
var length = 0;
// Get top element of stack
var temp = this.stack.top;
// Collects new solution
while (temp != null)
{
output[length] = temp.data;
//visit to next node
temp = temp.next;
length++;
}
// Update new length
this.result = this.stack.length;
}
}
}
this.sum_subsequence(collection, output, location - 1, sum, k + collection[location]);
//Remove a top element
this.stack.pop();
}
}
// Handles the request to find longest length sum
subsequences(collection, size, sum)
{
if (size <= 0)
{
return;
}
// Used to collect result
var output = Array(size).fill(0);
this.result = 0;
// Display given collection elements
process.stdout.write("\n Given collection \n");
this.display(collection, size);
this.sum_subsequence(collection, output, size - 1, sum, 0);
if (this.result > 0)
{
process.stdout.write("\n Longest subsequences of sum " + sum + " are \n");
this.display(output, this.result);
}
else
{
process.stdout.write("\n Subsequences of sum " + sum + " are not exist \n");
}
}
}
function main()
{
var obj = new Subsequence();
var collection = [5, 7, 2, 3, 4, 9, 1, -4, 10];
//Get the size
var size = collection.length;
// [ 5 2 3 4 -4 ]
// or
// [ 7 2 4 1 -4 ]
obj.subsequences(collection, size, 10);
}
main();
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
# Python 3 program
# Find longest length subsequence of given sum
# Stack Node
class Node :
def __init__(self, data) :
self.data = data
self.next = None
# Define custom stack and its operation
class MyStack :
def __init__(self) :
self.top = None
self.length = 0
# Add a new element in stack
def push(self, data) :
# Make a new stack node
new_node = Node(data)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
self.length += 1
else :
print("Memory overflow\n", end = "")
# remove a top element in stack
def pop(self) :
if (self.top != None) :
self.top = self.top.next
self.length -= 1
# check that whether stack is empty or not
def is_empty(self) :
if (self.top != None) :
return False
else :
return True
def is_size(self) :
return self.length
# Used to get top element of stack
def peek(self) :
if (self.top != None) :
return self.top.data
else :
return 0
class Subsequence :
def __init__(self) :
self.stack = MyStack()
self.result = 0
# Display given array elements
def display(self, collection, size) :
i = 0
while (i < size) :
print(" ", collection[i] ," ", end = "")
i += 1
# Find Longest subsequence of given sum
def sum_subsequence(self, collection, output, location, sum, k) :
if (location == -1) :
return
else :
self.sum_subsequence(collection, output, location - 1, sum, k)
# Add element into stack
self.stack.push(collection[location])
if (sum == k + collection[location]) :
# When subsequence sum is equal to given sum
if (self.stack.is_empty() == False) :
if (self.stack.length > self.result) :
# Get new solution
length = 0
# Get top element of stack
temp = self.stack.top
# Collects new solution
while (temp != None) :
output[length] = temp.data
# visit to next node
temp = temp.next
length += 1
# Update new length
self.result = self.stack.length
self.sum_subsequence(collection, output, location - 1, sum, k + collection[location])
# Remove a top element
self.stack.pop()
# Handles the request to find longest length sum
def subsequences(self, collection, size, sum) :
if (size <= 0) :
return
# Used to collect result
output = [0] * (size)
self.result = 0
# Display given collection elements
print("\n Given collection \n", end = "")
self.display(collection, size)
self.sum_subsequence(collection, output, size - 1, sum, 0)
if (self.result > 0) :
print("\n Longest subsequences of sum ", sum ," are \n", end = "")
self.display(output, self.result)
else :
print("\n Subsequences of sum ", sum ," are not exist \n", end = "")
def main() :
obj = Subsequence()
collection = [5, 7, 2, 3, 4, 9, 1, -4, 10]
# Get the size
size = len(collection)
# [ 5 2 3 4 -4 ]
# or
# [ 7 2 4 1 -4 ]
obj.subsequences(collection, size, 10)
if __name__ == "__main__": main()
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
# Ruby program
# Find longest length subsequence of given sum
# Stack Node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
# Define custom stack and its operation
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :length
attr_accessor :top, :length
def initialize()
self.top = nil
self.length = 0
end
# Add a new element in stack
def push(data)
# Make a new stack node
new_node = Node.new(data)
if (new_node != nil)
new_node.next = self.top
self.top = new_node
self.length += 1
else
print("Memory overflow\n")
end
end
# remove a top element in stack
def pop()
if (self.top != nil)
self.top = self.top.next
self.length -= 1
end
end
# check that whether stack is empty or not
def is_empty()
if (self.top != nil)
return false
else
return true
end
end
def is_size()
return self.length
end
# Used to get top element of stack
def peek()
if (self.top != nil)
return self.top.data
else
return 0
end
end
end
class Subsequence
# Define the accessor and reader of class Subsequence
attr_reader :stack, :result
attr_accessor :stack, :result
def initialize()
self.stack = MyStack.new()
self.result = 0
end
# Display given array elements
def display(collection, size)
i = 0
while (i < size)
print(" ", collection[i] ," ")
i += 1
end
end
# Find Longest subsequence of given sum
def sum_subsequence(collection, output, location, sum, k)
if (location == -1)
return
else
self.sum_subsequence(collection, output, location - 1, sum, k)
# Add element into stack
self.stack.push(collection[location])
if (sum == k + collection[location])
# When subsequence sum is equal to given sum
if (self.stack.is_empty() == false)
if (self.stack.length > self.result)
# Get new solution
length = 0
# Get top element of stack
temp = self.stack.top
# Collects new solution
while (temp != nil)
output[length] = temp.data
# visit to next node
temp = temp.next
length += 1
end
# Update new length
self.result = self.stack.length
end
end
end
self.sum_subsequence(collection, output, location - 1, sum, k + collection[location])
# Remove a top element
self.stack.pop()
end
end
# Handles the request to find longest length sum
def subsequences(collection, size, sum)
if (size <= 0)
return
end
# Used to collect result
output = Array.new(size) {0}
self.result = 0
# Display given collection elements
print("\n Given collection \n")
self.display(collection, size)
self.sum_subsequence(collection, output, size - 1, sum, 0)
if (self.result > 0)
print("\n Longest subsequences of sum ", sum ," are \n")
self.display(output, self.result)
else
print("\n Subsequences of sum ", sum ," are not exist \n")
end
end
end
def main()
obj = Subsequence.new()
collection = [5, 7, 2, 3, 4, 9, 1, -4, 10]
# Get the size
size = collection.length
# [ 5 2 3 4 -4 ]
# or
# [ 7 2 4 1 -4 ]
obj.subsequences(collection, size, 10)
end
main()
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
/*
Scala program
Find longest length subsequence of given sum
*/
//Stack Node
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
//Define custom stack and its operation
class MyStack(var top: Node,
var length: Int)
{
def this()
{
this(null, 0);
}
//Add a new element in stack
def push(data: Int): Unit = {
//Make a new stack node
var new_node: Node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
this.length += 1;
}
else
{
print("Memory overflow\n");
}
}
//remove a top element in stack
def pop(): Unit = {
if (this.top != null)
{
this.top = this.top.next;
this.length -= 1;
}
}
//check that whether stack is empty or not
def is_empty(): Boolean = {
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
def is_size(): Int = {
return this.length;
}
//Used to get top element of stack
def peek(): Int = {
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
class Subsequence(var stack: MyStack,
var result: Int)
{
def this()
{
this(new MyStack(), 0);
}
// Display given array elements
def display(collection: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + collection(i) + " ");
i += 1;
}
}
//Find Longest subsequence of given sum
def sum_subsequence(collection: Array[Int], output: Array[Int], location: Int, sum: Int, k: Int): Unit = {
if (location == -1)
{
return;
}
else
{
sum_subsequence(collection, output, location - 1, sum, k);
//Add element into stack
this.stack.push(collection(location));
if (sum == k + collection(location))
{
// When subsequence sum is equal to given sum
if (this.stack.is_empty() == false)
{
if (this.stack.length > this.result)
{
// Get new solution
var length: Int = 0;
// Get top element of stack
var temp: Node = this.stack.top;
// Collects new solution
while (temp != null)
{
output(length) = temp.data;
//visit to next node
temp = temp.next;
length += 1;
}
// Update new length
this.result = this.stack.length;
}
}
}
sum_subsequence(collection, output, location - 1, sum, k + collection(location));
//Remove a top element
this.stack.pop();
}
}
// Handles the request to find longest length sum
def subsequences(collection: Array[Int], size: Int, sum: Int): Unit = {
if (size <= 0)
{
return;
}
// Used to collect result
var output: Array[Int] = Array.fill[Int](size)(0);
this.result = 0;
// Display given collection elements
print("\n Given collection \n");
display(collection, size);
sum_subsequence(collection, output, size - 1, sum, 0);
if (this.result > 0)
{
print("\n Longest subsequences of sum " + sum + " are \n");
display(output, this.result);
}
else
{
print("\n Subsequences of sum " + sum + " are not exist \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Subsequence = new Subsequence();
var collection: Array[Int] = Array(5, 7, 2, 3, 4, 9, 1, -4, 10);
//Get the size
var size: Int = collection.length;
// [ 5 2 3 4 -4 ]
// or
// [ 7 2 4 1 -4 ]
obj.subsequences(collection, size, 10);
}
}
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
/*
Swift 4 program
Find longest length subsequence of given sum
*/
//Stack Node
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
//Define custom stack and its operation
class MyStack
{
var top: Node? ;
var length: Int;
init()
{
self.top = nil;
self.length = 0;
}
//Add a new element in stack
func push(_ data: Int)
{
//Make a new stack node
let new_node: Node? = Node(data);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
self.length += 1;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
//remove a top element in stack
func pop()
{
if (self.top != nil)
{
self.top = self.top!.next;
self.length -= 1;
}
}
//check that whether stack is empty or not
func is_empty() -> Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
func is_size() -> Int
{
return self.length;
}
//Used to get top element of stack
func peek() -> Int
{
if (self.top != nil)
{
return self.top!.data;
}
else
{
return 0;
}
}
}
class Subsequence
{
var stack: MyStack ;
var result: Int;
init()
{
self.stack = MyStack();
self.result = 0;
}
// Display given array elements
func display(_ collection: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", collection[i]," ", terminator: "");
i += 1;
}
}
//Find Longest subsequence of given sum
func sum_subsequence(_ collection: [Int], _ output: inout[Int], _ location: Int, _ sum: Int, _ k: Int)
{
if (location == -1)
{
return;
}
else
{
self.sum_subsequence(collection, &output, location - 1, sum, k);
//Add element into stack
self.stack.push(collection[location]);
if (sum == k + collection[location])
{
// When subsequence sum is equal to given sum
if (self.stack.is_empty() == false)
{
if (self.stack.length > self.result)
{
// Get new solution
var length: Int = 0;
// Get top element of stack
var temp: Node? = self.stack.top;
// Collects new solution
while (temp != nil)
{
output[length] = temp!.data;
//visit to next node
temp = temp!.next;
length += 1;
}
// Update new length
self.result = self.stack.length;
}
}
}
self.sum_subsequence(collection, &output, location - 1, sum, k + collection[location]);
//Remove a top element
self.stack.pop();
}
}
// Handles the request to find longest length sum
func subsequences(_ collection: [Int], _ size: Int, _ sum: Int)
{
if (size <= 0)
{
return;
}
// Used to collect result
var output: [Int] = Array(repeating: 0, count: size);
self.result = 0;
// Display given collection elements
print("\n Given collection \n", terminator: "");
self.display(collection, size);
self.sum_subsequence(collection, &output, size - 1, sum, 0);
if (self.result > 0)
{
print("\n Longest subsequences of sum ", sum ," are \n", terminator: "");
self.display(output, self.result);
}
else
{
print("\n Subsequences of sum ", sum ," are not exist \n", terminator: "");
}
}
}
func main()
{
let obj: Subsequence = Subsequence();
let collection: [Int] = [5, 7, 2, 3, 4, 9, 1, -4, 10];
//Get the size
let size: Int = collection.count;
// [5 2 3 4 -4 ]// or
// [7 2 4 1 -4 ]
obj.subsequences(collection, size, 10);
}
main();
Output
Given collection
5 7 2 3 4 9 1 -4 10
Longest subsequences of sum 10 are
5 2 3 4 -4
Time Complexity
The time complexity of the algorithm is O(2^n), where n is the number of elements in the input array. This is because for each element, we have two choices: include it or exclude it. Hence, there will be a total of 2^n possible subsequences. The recursive approach explores all possible combinations, leading to an exponential time complexity.
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