Find all subsequences with given sum
The problem "Find all subsequences with given sum" involves finding all the subsequences of a given array that have a specified sum. A subsequence is a sequence of elements that appear in the same order as they appear in the original array, but not necessarily consecutively. The sum of a subsequence is the sum of its elements.
Problem Statement
Given an array of integers and a target sum, we need to find all possible subsequences of the array whose sum is equal to the given target sum.
Example
Consider the following array and target sum:
Array: [5, 7, 2, 3, 4, 9, 1, -4, 10]
Target Sum: 10
The subsequences of the array with a sum of 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]
Idea to Solve the Problem
To find all the subsequences with a given sum, we can use recursion and a stack to keep track of the elements of the subsequence. We start with an empty stack and try two options at each step:
- Add the current element to the stack and recursively check for subsequences with the updated sum.
- Do not add the current element to the stack and recursively check for subsequences with the original sum.
We continue this process until we reach the end of the array. If the sum of the elements in the stack is equal to the target sum, we print the elements of the stack as a valid subsequence.
Algorithm
- Define a stack data structure to store the elements of the subsequence.
- Start a recursive function that takes the array, the stack, the current location, the target sum, and the current sum as parameters.
- In the recursive function, check if the current location is -1 (i.e., we have reached the end of the array). If yes, return from the function.
- Otherwise, call the recursive function twice:
- First, add the current element to the stack and update the current sum with the sum of the element and the current sum. Also, decrement the current location.
- Second, do not add the current element to the stack and keep the current sum unchanged. Only decrement the current location.
- After the recursive calls, if the current sum is equal to the target sum and the stack is not empty, print the elements of the stack as a valid subsequence.
- Continue the recursive calls until all possible combinations are explored.
Pseudocode
Function find_sum_sequence(array, stack, location, sum, k):
If location is -1:
Return
Call find_sum_sequence(array, stack, location - 1, sum, k)
Push array[location] onto the stack
Set sum = sum + array[location]
If sum is equal to k and stack is not empty:
Print the elements of the stack
Call find_sum_sequence(array, stack, location - 1, sum, k)
Pop an element from the stack
Function subsequences(array, size, sum):
If size is less than or equal to 0:
Return
Create an empty stack
Call find_sum_sequence(array, stack, size - 1, sum, 0)
Code Solution
// 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);
// Add element into stack
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);
// Add element into stack
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);
// Add element into stack
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);
// Add element into stack
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);
// Add element into stack
$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);
// Add element into stack
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)
# Add element into stack
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_reader :element, :next
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_reader :top
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)
# Add element into stack
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);
// Add element into stack
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);
// Add element into stack
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);
// Add element into stack
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 ]Time Complexity
The time complexity of the algorithm depends on the number of valid subsequences with the given sum. In the worst case, when all possible combinations are valid, the time complexity is O(2^n), where n is the size of the array. This is because, at each step, we have two choices: either include the current element in the subsequence or exclude it. The space complexity is O(n), where n is the size of the array, due to the space used by the stack.
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