Posted on by Kalkicode
Code Stack

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:

  1. Add the current element to the stack and recursively check for subsequences with the updated sum.
  2. 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

  1. Define a stack data structure to store the elements of the subsequence.
  2. Start a recursive function that takes the array, the stack, the current location, the target sum, and the current sum as parameters.
  3. 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.
  4. 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.
  5. 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.
  6. 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.

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