Find all subsequences with given sum

Here given code implementation process.

``````// C program
// Find all subsequences with given sum
#include <stdio.h>
#include <stdlib.h>

// Define stack
struct MyStack
{
int element;
struct MyStack *next;
};

// Add new element into 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 of stack
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *temp = *top;*top = temp->next;
free(temp);
temp = NULL;
}
}
// Display elements of given collection
void display(int collection[], int size)
{
printf("\n Given collection \n ");
for (int i = 0; i < size; ++i)
{
printf(" %d ", collection[i]);
}
}
//Display subsequences
void print_element(struct MyStack *top)
{
struct MyStack *temp = top;
printf(" [");
while (temp != NULL)
{
printf(" %d ", temp->element);
temp = temp->next;
}
printf("]\n");
}
// Find subsequences of given sum
void find_sum_sequence(int collection[], struct MyStack **top, int location, int sum, int k)
{
if (location == -1)
{
return;
}
else
{
find_sum_sequence(collection, top, location - 1, sum, k);
push(top, collection[location]);
if (sum == k + collection[location] && *top != NULL)
{
print_element( *top);
}
find_sum_sequence(collection, top, location - 1, sum, k + collection[location]);
// Remove top element of stack
pop(top);
}
}
// Handles the request to find Subsequence Sum
void subsequences(int collection[], int size, int sum)
{
if (size <= 0)
{
return;
}
// Display collection elements
display(collection, size);
// Define a stack
struct MyStack *top = NULL;
printf("\n All subsequences of sum %d are \n", sum);
// Find subsequences of given sum
find_sum_sequence(collection, & top, size - 1, sum, 0);
}
int main()
{
// Define array elements
int arr[] = {
5 , 7 , 2 , 3 , 4 , 9 , 1 , -4 , 10
};
//Get the size
int size = sizeof(arr) / sizeof(arr[0]);
int sum = 10;
//Test
subsequences(arr, size, sum);
sum = 6;
subsequences(arr, size, sum);
return 0;
}``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[ 7  3 ]
[ 5  2  3 ]
[ 7  2  1 ]
[ 5  4  1 ]
[ 2  3  4  1 ]
[ 9  1 ]
[ 5  7  2  -4 ]
[ 7  3  4  -4 ]
[ 5  2  3  4  -4 ]
[ 5  9  -4 ]
[ 2  3  9  -4 ]
[ 7  2  4  1  -4 ]
[ 4  9  1  -4 ]
[ 10 ]
[ 4  -4  10 ]
[ 3  1  -4  10 ]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[ 2  4 ]
[ 5  1 ]
[ 2  3  1 ]
[ 7  3  -4 ]
[ 5  2  3  -4 ]
[ 7  2  1  -4 ]
[ 5  4  1  -4 ]
[ 2  3  4  1  -4 ]
[ 9  1  -4 ]
[ -4  10 ]``````
``````/*
Java Program
Find all subsequences with given sum
*/
//Stack Node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element)
{
this.element = element;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public StackNode top;
public MyStack()
{
this.top = null;
}
//Add a new element in stack
public void push(int element)
{
//Make a new stack node
StackNode new_node = new StackNode(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
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;
}
}
//check that whether stack is empty or not
public boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
}
public class Subsequence
{

// Display elements of given collection
public void display(int[] collection, int size)
{
System.out.print("\n Given collection \n ");
for (int i = 0; i < size; ++i)
{
System.out.print("  " + collection[i] );
}
}
//Display subsequences
public void print_element(StackNode top)
{

StackNode temp = top;

System.out.print(" [");

while(temp != null)
{
System.out.print("  "+temp.element);

temp = temp.next;
}

System.out.print("]\n");
}

// Find subsequences of given sum
public void find_sum_sequence(int[] collection, MyStack stack, int location, int sum, int k)
{
if (location == -1)
{
return;
}
else
{
find_sum_sequence(collection, stack, location - 1, sum, k);
stack.push(collection[location]);
if (sum == k + collection[location] && stack.is_empty() == false)
{
print_element(stack.top);
}
find_sum_sequence(collection, stack, location - 1, sum, k + collection[location]);
// Remove top element of stack
stack.pop();
}
}
// Handles the request to find Subsequence Sum
public void subsequences(int[] collection, int size, int sum)
{
if (size <= 0)
{
return;
}
// Display collection elements
display(collection, size);
// Define a stack
MyStack stack = new MyStack();
System.out.print("\n All subsequences of sum " + sum + " are \n");
// Find subsequences of given sum
find_sum_sequence(collection, stack, size - 1, sum, 0);
}
public static void main(String[] args)
{

Subsequence obj = new Subsequence();
// Define array elements
int[] arr =
{
5 , 7 , 2 , 3 , 4 , 9 , 1 , -4 , 10
};
//Get the size
int size = arr.length;

//Test Case
int sum = 10;
obj.subsequences(arr, size, sum);
sum = 6;
obj.subsequences(arr, size, sum);

}
}

``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3]
[  5  2  3]
[  7  2  1]
[  5  4  1]
[  2  3  4  1]
[  9  1]
[  5  7  2  -4]
[  7  3  4  -4]
[  5  2  3  4  -4]
[  5  9  -4]
[  2  3  9  -4]
[  7  2  4  1  -4]
[  4  9  1  -4]
[  10]
[  4  -4  10]
[  3  1  -4  10]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4]
[  5  1]
[  2  3  1]
[  7  3  -4]
[  5  2  3  -4]
[  7  2  1  -4]
[  5  4  1  -4]
[  2  3  4  1  -4]
[  9  1  -4]
[  -4  10]``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Find all subsequences with given sum
*/

// Stack Node
class StackNode
{
public:
int element;
StackNode *next;
StackNode(int element)
{
this->element = element;
this->next = NULL;
}
};
// Define custom stack and its operation
class MyStack
{
public:
StackNode *top;
MyStack()
{
this->top = NULL;
}
// Add a new element in stack
void push(int element)
{
// Make a new stack node
StackNode *new_node = new StackNode(element);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
}
else
{
cout << "Memory overflow\n";
}
}
// remove a top element in stack
void pop()
{
if (this->top != NULL)
{
this->top = this->top->next;
}
}
// check that whether stack is empty or not
bool is_empty()
{
if (this->top != NULL)
{
return false;
}
else
{
return true;
}
}
};
class Subsequence
{
public:
//  Display elements of given collection
void display(int collection[], int size)
{
cout << "\n Given collection \n ";
for (int i = 0; i < size; ++i)
{
cout << "  " << collection[i];
}
}
// Display subsequences
void print_element(StackNode *top)
{
StackNode *temp = top;
cout << " [";
while (temp != NULL)
{
cout << "  " << temp->element;
temp = temp->next;
}
cout << "]\n";
}
//  Find subsequences of given sum
void find_sum_sequence(int collection[], MyStack stack, int location, int sum, int k)
{
if (location == -1)
{
return;
}
else
{
this->find_sum_sequence(collection, stack, location - 1, sum, k);
stack.push(collection[location]);
if (sum == k + collection[location] && stack.is_empty() == false)
{
this->print_element(stack.top);
}
this->find_sum_sequence(collection, stack, location - 1, sum, k + collection[location]);
//  Remove top element of stack
stack.pop();
}
}
//  Handles the request to find Subsequence Sum
void subsequences(int collection[], int size, int sum)
{
if (size <= 0)
{
return;
}
//  Display collection elements
this->display(collection, size);
//  Define a stack
MyStack stack = MyStack();
cout << "\n All subsequences of sum " << sum << " are \n";
//  Find subsequences of given sum
this->find_sum_sequence(collection, stack, size - 1, sum, 0);
}
};
int main()
{
Subsequence obj = Subsequence();
//  Define array elements
int arr[] = {
5 , 7 , 2 , 3 , 4 , 9 , 1 , -4 , 10
};
// Get the size
int size = sizeof(arr) / sizeof(arr[0]);
// Test Case
int sum = 10;
obj.subsequences(arr, size, sum);
sum = 6;
obj.subsequences(arr, size, sum);
return 0;
}``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3]
[  5  2  3]
[  7  2  1]
[  5  4  1]
[  2  3  4  1]
[  9  1]
[  5  7  2  -4]
[  7  3  4  -4]
[  5  2  3  4  -4]
[  5  9  -4]
[  2  3  9  -4]
[  7  2  4  1  -4]
[  4  9  1  -4]
[  10]
[  4  -4  10]
[  3  1  -4  10]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4]
[  5  1]
[  2  3  1]
[  7  3  -4]
[  5  2  3  -4]
[  7  2  1  -4]
[  5  4  1  -4]
[  2  3  4  1  -4]
[  9  1  -4]
[  -4  10]``````
``````// Include namespace system
using System;
/*
C# Program
Find all subsequences with given sum
*/
// Stack Node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element)
{
this.element = element;
this.next = null;
}
}
// Define custom stack and its operation
public class MyStack
{
public StackNode top;
public MyStack()
{
this.top = null;
}
// Add a new element in stack
public void push(int element)
{
// Make a new stack node
StackNode new_node = new StackNode(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
Console.Write("Memory overflow\n");
}
}
// remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
// check that whether stack is empty or not
public Boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
}
public class Subsequence
{
//  Display elements of given collection
public void display(int[] collection, int size)
{
Console.Write("\n Given collection \n ");
for (int i = 0; i < size; ++i)
{
Console.Write("  " + collection[i]);
}
}
// Display subsequences
public void print_element(StackNode top)
{
StackNode temp = top;
Console.Write(" [");
while (temp != null)
{
Console.Write("  " + temp.element);
temp = temp.next;
}
Console.Write("]\n");
}
//  Find subsequences of given sum
public void find_sum_sequence(int[] collection, MyStack stack, int location, int sum, int k)
{
if (location == -1)
{
return;
}
else
{
find_sum_sequence(collection, stack, location - 1, sum, k);
stack.push(collection[location]);
if (sum == k + collection[location] && stack.is_empty() == false)
{
print_element(stack.top);
}
find_sum_sequence(collection, stack, location - 1, sum, k + collection[location]);
//  Remove top element of stack
stack.pop();
}
}
//  Handles the request to find Subsequence Sum
public void subsequences(int[] collection, int size, int sum)
{
if (size <= 0)
{
return;
}
//  Display collection elements
display(collection, size);
//  Define a stack
MyStack stack = new MyStack();
Console.Write("\n All subsequences of sum " + sum + " are \n");
//  Find subsequences of given sum
find_sum_sequence(collection, stack, size - 1, sum, 0);
}
public static void Main(String[] args)
{
Subsequence obj = new Subsequence();
//  Define array elements
int[] arr = {
5 , 7 , 2 , 3 , 4 , 9 , 1 , -4 , 10
};
// Get the size
int size = arr.Length;
// Test Case
int sum = 10;
obj.subsequences(arr, size, sum);
sum = 6;
obj.subsequences(arr, size, sum);
}
}``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3]
[  5  2  3]
[  7  2  1]
[  5  4  1]
[  2  3  4  1]
[  9  1]
[  5  7  2  -4]
[  7  3  4  -4]
[  5  2  3  4  -4]
[  5  9  -4]
[  2  3  9  -4]
[  7  2  4  1  -4]
[  4  9  1  -4]
[  10]
[  4  -4  10]
[  3  1  -4  10]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4]
[  5  1]
[  2  3  1]
[  7  3  -4]
[  5  2  3  -4]
[  7  2  1  -4]
[  5  4  1  -4]
[  2  3  4  1  -4]
[  9  1  -4]
[  -4  10]``````
``````<?php
/*
Php Program
Find all subsequences with given sum
*/
// Stack Node
class StackNode
{
public \$element;
public \$next;

function __construct(\$element)
{
\$this->element = \$element;
\$this->next = null;
}
}
// Define custom stack and its operation
class MyStack
{
public \$top;

function __construct()
{
\$this->top = null;
}
// Add a new element in stack
public	function push(\$element)
{
// Make a new stack node
\$new_node = new StackNode(\$element);
if (\$new_node != null)
{
\$new_node->next = \$this->top;
\$this->top = \$new_node;
}
else
{
echo "Memory overflow\n";
}
}
// remove a top element in stack
public	function pop()
{
if (\$this->top != null)
{
\$this->top = \$this->top->next;
}
}
// check that whether stack is empty or not
public	function is_empty()
{
if (\$this->top != null)
{
return false;
}
else
{
return true;
}
}
}
class Subsequence
{
//  Display elements of given collection
public	function display( \$collection, \$size)
{
echo "\n Given collection \n ";
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$collection[\$i];
}
}
// Display subsequences
public	function print_element(\$top)
{
\$temp = \$top;
echo " [";
while (\$temp != null)
{
echo "  ". \$temp->element;
\$temp = \$temp->next;
}
echo "]\n";
}
//  Find subsequences of given sum
public	function find_sum_sequence( \$collection, \$stack, \$location, \$sum, \$k)
{
if (\$location == -1)
{
return;
}
else
{
\$this->find_sum_sequence(\$collection, \$stack, \$location - 1, \$sum, \$k);
\$stack->push(\$collection[\$location]);
if (\$sum == \$k + \$collection[\$location] && \$stack->is_empty() == false)
{
\$this->print_element(\$stack->top);
}
\$this->find_sum_sequence(\$collection, \$stack, \$location - 1, \$sum, \$k + \$collection[\$location]);
//  Remove top element of stack
\$stack->pop();
}
}
//  Handles the request to find Subsequence Sum
public	function subsequences( \$collection, \$size, \$sum)
{
if (\$size <= 0)
{
return;
}
//  Display collection elements
\$this->display(\$collection, \$size);
//  Define a stack
\$stack = new MyStack();
echo "\n All subsequences of sum ". \$sum ." are \n";
//  Find subsequences of given sum
\$this->find_sum_sequence(\$collection, \$stack, \$size - 1, \$sum, 0);
}
}

function main()
{
\$obj = new Subsequence();
//  Define array elements
\$arr = array(5, 7, 2, 3, 4, 9, 1, -4, 10);
// Get the size
\$size = count(\$arr);
// Test Case
\$sum = 10;
\$obj->subsequences(\$arr, \$size, \$sum);
\$sum = 6;
\$obj->subsequences(\$arr, \$size, \$sum);
}
main();``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3]
[  5  2  3]
[  7  2  1]
[  5  4  1]
[  2  3  4  1]
[  9  1]
[  5  7  2  -4]
[  7  3  4  -4]
[  5  2  3  4  -4]
[  5  9  -4]
[  2  3  9  -4]
[  7  2  4  1  -4]
[  4  9  1  -4]
[  10]
[  4  -4  10]
[  3  1  -4  10]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4]
[  5  1]
[  2  3  1]
[  7  3  -4]
[  5  2  3  -4]
[  7  2  1  -4]
[  5  4  1  -4]
[  2  3  4  1  -4]
[  9  1  -4]
[  -4  10]``````
``````/*
Node Js Program
Find all subsequences with given sum
*/
// Stack Node
class StackNode
{
constructor(element)
{
this.element = element;
this.next = null;
}
}
// Define custom stack and its operation
class MyStack
{
constructor()
{
this.top = null;
}
// Add a new element in stack
push(element)
{
// Make a new stack node
var new_node = new StackNode(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
process.stdout.write("Memory overflow\n");
}
}
// remove a top element in stack
pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
// check that whether stack is empty or not
is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
}
class Subsequence
{
//  Display elements of given collection
display(collection, size)
{
process.stdout.write("\n Given collection \n ");
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + collection[i]);
}
}
// Display subsequences
print_element(top)
{
var temp = top;
process.stdout.write(" [");
while (temp != null)
{
process.stdout.write("  " + temp.element);
temp = temp.next;
}
process.stdout.write("]\n");
}
//  Find subsequences of given sum
find_sum_sequence(collection, stack, location, sum, k)
{
if (location == -1)
{
return;
}
else
{
this.find_sum_sequence(collection, stack, location - 1, sum, k);
stack.push(collection[location]);
if (sum == k + collection[location] && stack.is_empty() == false)
{
this.print_element(stack.top);
}
this.find_sum_sequence(collection, stack, location - 1, sum, k + collection[location]);
//  Remove top element of stack
stack.pop();
}
}
//  Handles the request to find Subsequence Sum
subsequences(collection, size, sum)
{
if (size <= 0)
{
return;
}
//  Display collection elements
this.display(collection, size);
//  Define a stack
var stack = new MyStack();
process.stdout.write("\n All subsequences of sum " + sum + " are \n");
//  Find subsequences of given sum
this.find_sum_sequence(collection, stack, size - 1, sum, 0);
}
}

function main()
{
var obj = new Subsequence();
//  Define array elements
var arr = [5, 7, 2, 3, 4, 9, 1, -4, 10];
// Get the size
var size = arr.length;
// Test Case
var sum = 10;
obj.subsequences(arr, size, sum);
sum = 6;
obj.subsequences(arr, size, sum);
}
main();``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3]
[  5  2  3]
[  7  2  1]
[  5  4  1]
[  2  3  4  1]
[  9  1]
[  5  7  2  -4]
[  7  3  4  -4]
[  5  2  3  4  -4]
[  5  9  -4]
[  2  3  9  -4]
[  7  2  4  1  -4]
[  4  9  1  -4]
[  10]
[  4  -4  10]
[  3  1  -4  10]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4]
[  5  1]
[  2  3  1]
[  7  3  -4]
[  5  2  3  -4]
[  7  2  1  -4]
[  5  4  1  -4]
[  2  3  4  1  -4]
[  9  1  -4]
[  -4  10]``````
``````#   Python 3 Program
#   Find all subsequences with given sum

# Stack Node
class StackNode :

def __init__(self, element) :
self.element = element
self.next = None

# Define custom stack and its operation
class MyStack :

def __init__(self) :
self.top = None

# Add a new element in stack
def push(self, element) :
# Make a new stack node
new_node = StackNode(element)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
else :
print("Memory overflow\n", end = "")

# remove a top element in stack
def pop(self) :
if (self.top != None) :
self.top = self.top.next

# check that whether stack is empty or not
def is_empty(self) :
if (self.top != None) :
return False
else :
return True

class Subsequence :
#  Display elements of given collection
def display(self, collection, size) :
print("\n Given collection \n ", end = "")
i = 0
while (i < size) :
print("  ", collection[i], end = "")
i += 1

# Display subsequences
def print_element(self, top) :
temp = top
print(" [", end = "")
while (temp != None) :
print("  ", temp.element, end = "")
temp = temp.next

print("]\n", end = "")

#  Find subsequences of given sum
def find_sum_sequence(self, collection, stack, location, sum, k) :
if (location == -1) :
return
else :
self.find_sum_sequence(collection, stack, location - 1, sum, k)
stack.push(collection[location])
if (sum == k + collection[location] and stack.is_empty() == False) :
self.print_element(stack.top)

self.find_sum_sequence(collection, stack, location - 1, sum, k + collection[location])
#  Remove top element of stack
stack.pop()

#  Handles the request to find Subsequence Sum
def subsequences(self, collection, size, sum) :
if (size <= 0) :
return

#  Display collection elements
self.display(collection, size)
#  Define a stack
stack = MyStack()
print("\n All subsequences of sum ", sum ," are \n", end = "")
#  Find subsequences of given sum
self.find_sum_sequence(collection, stack, size - 1, sum, 0)

def main() :
obj = Subsequence()
#  Define array elements
arr = [5, 7, 2, 3, 4, 9, 1, -4, 10]
# Get the size
size = len(arr)
# Test Case
sum = 10
obj.subsequences(arr, size, sum)
sum = 6
obj.subsequences(arr, size, sum)

if __name__ == "__main__": main()``````

Output

`````` Given collection
5   7   2   3   4   9   1   -4   10
All subsequences of sum  10  are
[   7   3]
[   5   2   3]
[   7   2   1]
[   5   4   1]
[   2   3   4   1]
[   9   1]
[   5   7   2   -4]
[   7   3   4   -4]
[   5   2   3   4   -4]
[   5   9   -4]
[   2   3   9   -4]
[   7   2   4   1   -4]
[   4   9   1   -4]
[   10]
[   4   -4   10]
[   3   1   -4   10]

Given collection
5   7   2   3   4   9   1   -4   10
All subsequences of sum  6  are
[   2   4]
[   5   1]
[   2   3   1]
[   7   3   -4]
[   5   2   3   -4]
[   7   2   1   -4]
[   5   4   1   -4]
[   2   3   4   1   -4]
[   9   1   -4]
[   -4   10]``````
``````#  Ruby Program
#  Find all subsequences with given sum

# Stack Node
class StackNode
# Define the accessor and reader of class StackNode
attr_accessor :element, :next

def initialize(element)
self.element = element
self.next = nil
end

end

# Define custom stack and its operation
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top

def initialize()
self.top = nil
end

# Add a new element in stack
def push(element)
# Make a new stack node
new_node = StackNode.new(element)
if (new_node != nil)
new_node.next = self.top
self.top = new_node
else
print("Memory overflow\n")
end

end

# remove a top element in stack
def pop()
if (self.top != nil)
self.top = self.top.next
end

end

# check that whether stack is empty or not
def is_empty()
if (self.top != nil)
return false
else
return true
end

end

end

class Subsequence
#  Display elements of given collection
def display(collection, size)
print("\n Given collection \n ")
i = 0
while (i < size)
print("  ", collection[i])
i += 1
end

end

# Display subsequences
def print_element(top)
temp = top
print(" [")
while (temp != nil)
print("  ", temp.element)
temp = temp.next
end

print(" ]\n")
end

#  Find subsequences of given sum
def find_sum_sequence(collection, stack, location, sum, k)
if (location == -1)
return
else
self.find_sum_sequence(collection, stack, location - 1, sum, k)
stack.push(collection[location])
if (sum == k + collection[location] && stack.is_empty() == false)
self.print_element(stack.top)
end

self.find_sum_sequence(collection, stack, location - 1, sum, k + collection[location])
#  Remove top element of stack
stack.pop()
end

end

#  Handles the request to find Subsequence Sum
def subsequences(collection, size, sum)
if (size <= 0)
return
end

#  Display collection elements
self.display(collection, size)
#  Define a stack
stack = MyStack.new()
print("\n All subsequences of sum ", sum ," are \n")
#  Find subsequences of given sum
self.find_sum_sequence(collection, stack, size - 1, sum, 0)
end

end

def main()
obj = Subsequence.new()
#  Define array elements
arr = [5, 7, 2, 3, 4, 9, 1, -4, 10]
# Get the size
size = arr.length
# Test Case
sum = 10
obj.subsequences(arr, size, sum)
sum = 6
obj.subsequences(arr, size, sum)
end

main()``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3 ]
[  5  2  3 ]
[  7  2  1 ]
[  5  4  1 ]
[  2  3  4  1 ]
[  9  1 ]
[  5  7  2  -4 ]
[  7  3  4  -4 ]
[  5  2  3  4  -4 ]
[  5  9  -4 ]
[  2  3  9  -4 ]
[  7  2  4  1  -4 ]
[  4  9  1  -4 ]
[  10 ]
[  4  -4  10 ]
[  3  1  -4  10 ]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4 ]
[  5  1 ]
[  2  3  1 ]
[  7  3  -4 ]
[  5  2  3  -4 ]
[  7  2  1  -4 ]
[  5  4  1  -4 ]
[  2  3  4  1  -4 ]
[  9  1  -4 ]
[  -4  10 ]
``````
``````/*
Scala Program
Find all subsequences with given sum
*/
// Stack Node
class StackNode(var element: Int , var next: StackNode)
{
def this(element: Int)
{
this(element, null);
}
}
// Define custom stack and its operation
class MyStack(var top: StackNode)
{
def this()
{
this(null);
}
// Add a new element in stack
def push(element: Int): Unit = {
// Make a new stack node
var new_node: StackNode = new StackNode(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
print("Memory overflow\n");
}
}
// remove a top element in stack
def pop(): Unit = {
if (this.top != null)
{
this.top = this.top.next;
}
}
// check that whether stack is empty or not
def is_empty(): Boolean = {
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
}
class Subsequence
{
//  Display elements of given collection
def display(collection: Array[Int], size: Int): Unit = {
print("\n Given collection \n ");
var i: Int = 0;
while (i < size)
{
print("  " + collection(i));
i += 1;
}
}
// Display subsequences
def print_element(top: StackNode): Unit = {
var temp: StackNode = top;
print(" [");
while (temp != null)
{
print("  " + temp.element);
temp = temp.next;
}
print(" ]\n");
}
//  Find subsequences of given sum
def find_sum_sequence(collection: Array[Int], stack: MyStack, location: Int, sum: Int, k: Int): Unit = {
if (location == -1)
{
return;
}
else
{
this.find_sum_sequence(collection, stack, location - 1, sum, k);
stack.push(collection(location));
if (sum == k + collection(location) && stack.is_empty() == false)
{
this.print_element(stack.top);
}
this.find_sum_sequence(collection, stack, location - 1, sum, k + collection(location));
//  Remove top element of stack
stack.pop();
}
}
//  Handles the request to find Subsequence Sum
def subsequences(collection: Array[Int], size: Int, sum: Int): Unit = {
if (size <= 0)
{
return;
}
//  Display collection elements
this.display(collection, size);
//  Define a stack
var stack: MyStack = new MyStack();
print("\n All subsequences of sum " + sum + " are \n");
//  Find subsequences of given sum
this.find_sum_sequence(collection, stack, size - 1, sum, 0);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Subsequence = new Subsequence();
//  Define array elements
var arr: Array[Int] = Array(5, 7, 2, 3, 4, 9, 1, -4, 10);
// Get the size
var size: Int = arr.length;
// Test Case
var sum: Int = 10;
obj.subsequences(arr, size, sum);
sum = 6;
obj.subsequences(arr, size, sum);
}
}``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3 ]
[  5  2  3 ]
[  7  2  1 ]
[  5  4  1 ]
[  2  3  4  1 ]
[  9  1 ]
[  5  7  2  -4 ]
[  7  3  4  -4 ]
[  5  2  3  4  -4 ]
[  5  9  -4 ]
[  2  3  9  -4 ]
[  7  2  4  1  -4 ]
[  4  9  1  -4 ]
[  10 ]
[  4  -4  10 ]
[  3  1  -4  10 ]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4 ]
[  5  1 ]
[  2  3  1 ]
[  7  3  -4 ]
[  5  2  3  -4 ]
[  7  2  1  -4 ]
[  5  4  1  -4 ]
[  2  3  4  1  -4 ]
[  9  1  -4 ]
[  -4  10 ]``````
``````/*
Swift 4 Program
Find all subsequences with given sum
*/
// Stack Node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int)
{
self.element = element;
self.next = nil;
}
}
// Define custom stack and its operation
class MyStack
{
var top: StackNode? ;
init()
{
self.top = nil;
}
// Add a new element in stack
func push(_ element: Int)
{
// Make a new stack node
let new_node: StackNode? = StackNode(element);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
// remove a top element in stack
func pop()
{
if (self.top != nil)
{
self.top = self.top!.next;
}
}
// check that whether stack is empty or not
func is_empty()->Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
}
class Subsequence
{
//  Display elements of given collection
func display(_ collection: [Int], _ size: Int)
{
print("\n Given collection \n ", terminator: "");
var i: Int = 0;
while (i < size)
{
print("  ", collection[i], terminator: "");
i += 1;
}
}
// Display subsequences
func print_element(_ top: StackNode? )
{
var temp: StackNode? = top;
print(" [", terminator: "");
while (temp != nil)
{
print("  ", temp!.element, terminator: "");
temp = temp!.next;
}
print(" ]\n", terminator: "");
}
//  Find subsequences of given sum
func find_sum_sequence(_ collection: [Int], _ stack: MyStack, _ location: Int, _ sum: Int, _ k: Int)
{
if (location == -1)
{
return;
}
else
{
self.find_sum_sequence(collection, stack, location - 1, sum, k);
stack.push(collection[location]);
if (sum == k + collection[location] && stack.is_empty() == false)
{
self.print_element(stack.top);
}
self.find_sum_sequence(collection, stack, location - 1, sum, k + collection[location]);
//  Remove top element of stack
stack.pop();
}
}
//  Handles the request to find Subsequence Sum
func subsequences(_ collection: [Int], _ size: Int, _ sum: Int)
{
if (size <= 0)
{
return;
}
//  Display collection elements
self.display(collection, size);
//  Define a stack
let stack: MyStack = MyStack();
print("\n All subsequences of sum ", sum ," are ");
//  Find subsequences of given sum
self.find_sum_sequence(collection, stack, size - 1, sum, 0);
}
}
func main()
{
let obj: Subsequence = Subsequence();
//  Define array elements
let arr: [Int] = [5, 7, 2, 3, 4, 9, 1, -4, 10];
// Get the size
let size: Int = arr.count;
// Test Case
var sum: Int = 10;
obj.subsequences(arr, size, sum);
sum = 6;
obj.subsequences(arr, size, sum);
}
main();``````

Output

`````` Given collection
5   7   2   3   4   9   1   -4   10
All subsequences of sum  10  are
[   7   3 ]
[   5   2   3 ]
[   7   2   1 ]
[   5   4   1 ]
[   2   3   4   1 ]
[   9   1 ]
[   5   7   2   -4 ]
[   7   3   4   -4 ]
[   5   2   3   4   -4 ]
[   5   9   -4 ]
[   2   3   9   -4 ]
[   7   2   4   1   -4 ]
[   4   9   1   -4 ]
[   10 ]
[   4   -4   10 ]
[   3   1   -4   10 ]

Given collection
5   7   2   3   4   9   1   -4   10
All subsequences of sum  6  are
[   2   4 ]
[   5   1 ]
[   2   3   1 ]
[   7   3   -4 ]
[   5   2   3   -4 ]
[   7   2   1   -4 ]
[   5   4   1   -4 ]
[   2   3   4   1   -4 ]
[   9   1   -4 ]
[   -4   10 ]``````
``````/*
Kotlin Program
Find all subsequences with given sum
*/
// Stack Node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int)
{
this.element = element;
this.next = null;
}
}
// Define custom stack and its operation
class MyStack
{
var top: StackNode ? ;
constructor()
{
this.top = null;
}
// Add a new element in stack
fun push(element: Int): Unit
{
// Make a new stack node
var new_node: StackNode? = StackNode(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
print("Memory overflow\n");
}
}
// remove a top element in stack
fun pop(): Unit
{
if (this.top != null)
{
this.top = this.top?.next;
}
}
// check that whether stack is empty or not
fun is_empty(): Boolean
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
}
class Subsequence
{
//  Display elements of given collection
fun display(collection: Array < Int > , size: Int): Unit
{
print("\n Given collection \n ");
var i: Int = 0;
while (i < size)
{
print("  " + collection[i]);
i += 1;
}
}
// Display subsequences
fun print_element(top: StackNode ? ): Unit
{
var temp: StackNode ? = top;
print(" [");
while (temp != null)
{
print("  " + temp.element);
temp = temp.next;
}
print(" ]\n");
}
//  Find subsequences of given sum
fun find_sum_sequence(collection: Array < Int > , stack: MyStack , location : Int, sum: Int, k: Int): Unit
{
if (location == -1)
{
return;
}
else
{
this.find_sum_sequence(collection, stack, location - 1, sum, k);
stack.push(collection[location]);
if (sum == k + collection[location] && stack.is_empty() == false)
{
this.print_element(stack.top);
}
this.find_sum_sequence(collection, stack, location - 1, sum, k + collection[location]);
//  Remove top element of stack
stack.pop();
}
}
//  Handles the request to find Subsequence Sum
fun subsequences(collection: Array < Int > , size: Int, sum: Int): Unit
{
if (size <= 0)
{
return;
}
//  Display collection elements
this.display(collection, size);
//  Define a stack
var stack: MyStack = MyStack();
print("\n All subsequences of sum " + sum + " are \n");
//  Find subsequences of given sum
this.find_sum_sequence(collection, stack, size - 1, sum, 0);
}
}
fun main(args: Array < String > ): Unit
{
var obj: Subsequence = Subsequence();
//  Define array elements
var arr: Array < Int > = arrayOf(5, 7, 2, 3, 4, 9, 1, -4, 10);
// Get the size
var size: Int = arr.count();
// Test Case
var sum: Int = 10;
obj.subsequences(arr, size, sum);
sum = 6;
obj.subsequences(arr, size, sum);
}``````

Output

`````` Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 10 are
[  7  3 ]
[  5  2  3 ]
[  7  2  1 ]
[  5  4  1 ]
[  2  3  4  1 ]
[  9  1 ]
[  5  7  2  -4 ]
[  7  3  4  -4 ]
[  5  2  3  4  -4 ]
[  5  9  -4 ]
[  2  3  9  -4 ]
[  7  2  4  1  -4 ]
[  4  9  1  -4 ]
[  10 ]
[  4  -4  10 ]
[  3  1  -4  10 ]

Given collection
5  7  2  3  4  9  1  -4  10
All subsequences of sum 6 are
[  2  4 ]
[  5  1 ]
[  2  3  1 ]
[  7  3  -4 ]
[  5  2  3  -4 ]
[  7  2  1  -4 ]
[  5  4  1  -4 ]
[  2  3  4  1  -4 ]
[  9  1  -4 ]
[  -4  10 ]``````

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.