Posted on by Kalkicode
Code Stack

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

  1. Create a stack data structure to hold the elements of the current subsequence.
  2. Traverse the array from the last element to the first element.
  3. For each element at index i in the array: a. Call the recursive function sum_subsequence with the array, an output array, the index i-1, the target sum, and the current sum (k) set to 0. b. Push the element at index i 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 function sum_subsequence with the array, the output array, the index i-1, the target sum, and the updated current sum (k + collection[i]). e. Pop the element from the stack.
  4. 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.

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