Posted on by Kalkicode
Code Backtracking

Find all subsequences with given sum and length

In this article, we will explore a problem where we need to find all subsequences of a given array that have a specific sum and length. We will provide a detailed explanation of the problem, present a suitable example, discuss the algorithm and pseudocode, and explain the resulting output. The time complexity of the code will also be analyzed.

Introduction

The problem at hand involves finding subsequences of a given array that satisfy two conditions: the subsequence should have a specific length, and the sum of its elements should be equal to a given sum. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Problem Statement

Given an array of integers, we are tasked with finding all subsequences that have a specific length, k, and a sum equal to a given value, sum. We need to output all such subsequences.

Example

Let's consider the following array:

arr[] = {1, 9, 8, -4, 2, 3, 5, 6}

We want to find all subsequences of length 3 with a sum of 10.

Algorithm and Pseudocode

To solve this problem, we can use a recursive approach. The algorithm can be outlined as follows:

  1. Create a function, show(), to display the elements of a subsequence.
  2. Implement a recursive function, subsequence(), to generate all possible subsequences.
  3. If the length of the current subsequence, j, is equal to k and the sum of its elements, sum, is equal to the desired sum, we display the subsequence using the show() function.
  4. If we have processed all elements in the array or if j is greater than or equal to k, we stop the execution of the current subsequence.
  5. Assign the current element, arr[i], to the output array at index j and call the subsequence() function recursively.
  6. Increment i and j, and call the subsequence() function recursively again to explore other possibilities.
  7. Create a function, findSubsequence(), to handle the request of finding subsequences with the given sum and length.
  8. Inside the findSubsequence() function, initialize an output array of length k.
  9. Call the subsequence() function with appropriate parameters to generate all valid subsequences.

The pseudocode for the algorithm is as follows:

function show(arr, n):
    for i = 0 to n:
        print arr[i]
    print new line

function subsequence(arr, output, i, j, n, k, sum, result):
    if j equals k and sum equals result:
        show(output, k)
    if i equals n or j is greater than or equal to k:
        return
    output[j] = arr[i]
    subsequence(arr, output, i + 1, j + 1, n, k, sum, result + arr[i])
    subsequence(arr, output, i + 1, j, n, k, sum, result)

function findSubsequence(arr, n, k, sum):
    if k is less than or equal to 0 or n is less than or equal to 0:
        return
    result[k]
    print "Subsequence sum:", sum
    print "Length:", k
    subsequence(arr, result, 0, 0, n, k, sum, 0)

main:
    arr = [1, 9, 8, -4, 2, 3, 5, 6]
    n = size of arr
    k = 3
    sum = 10
    findSubsequence(arr, n, k, sum)

Code Solution

Here given code implementation process.

// C program 
// 
#include <stdio.h>

// Display result
void show(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf(" %d", arr[i]);
	}
	printf("\n");
}
void subsequence(int arr[], int output[], int i, int j, int n, int k, int sum, int result)
{
	if (j == k && sum == result)
	{
		show(output, k);
	}
	if (i == n || j >= k)
	{
		// Stop execution process
		return;
	}
	// Get element
	output[j] = arr[i];
	subsequence(arr, output, i + 1, j + 1, n, k, sum, result + arr[i]);
	subsequence(arr, output, i + 1, j, n, k, sum, result);
}
// Handles the request of find all sequences with given sum and length k
void findSubsequence(int arr[], int n, int k, int sum)
{
	if (k <= 0 || n <= 0)
	{
		return;
	}
	// Used to collect Subsequence element
	int result[k];
	printf("\n Subsequence sum : %d", sum);
	printf("\n Length : %d\n", k);
	subsequence(arr, result, 0, 0, n, k, sum, 0);
}
int main()
{
	int arr[] = {
		1 , 9 , 8 , -4 , 2 , 3 , 5 , 6
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 3;
	int sum = 10;
	// Test case
	findSubsequence(arr, n, k, sum);
	return 0;
}

Output

 Subsequence sum : 10
 Length : 3
 1 3 6
 9 -4 5
 8 -4 6
 2 3 5
/*
    Java Program for
    Find all subsequences with given sum and length
*/
public class Subsequence
{
	// Display result
	public void show(int[] output, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print("  " + output[i]);
		}
		System.out.print("\n");
	}
	// Find and print the all subsequences of given sum and length
	public void subsequenceSum(int[] arr, int[] output, int i, int j, int n, int k, int sum, int result)
	{
		if (j == k && sum == result)
		{
			// Get subsequence with given sum and length
			show(output, k);
		}
		if (i == n || j >= k)
		{
			// Stop execution process
			return;
		}
		// Get element
		output[j] = arr[i];
		subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr[i]);
		subsequenceSum(arr, output, i + 1, j, n, k, sum, result);
	}
	// Handles the request of find all sequences with given sum and length k
	public void findSubsequence(int[] arr, int n, int k, int sum)
	{
		if (k <= 0 || n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		int[] result = new int[k];
		System.out.print("\n Subsequence sum : " + sum);
		System.out.print("\n Length : " + k + "\n");
		subsequenceSum(arr, result, 0, 0, n, k, sum, 0);
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		int[] arr = {
			1 , 9 , 8 , -4 , 2 , 3 , 5 , 6
		};
		int n = arr.length;
		int k = 3;
		int sum = 10;
		// Test case
		task.findSubsequence(arr, n, k, sum);
	}
}

Output

 Subsequence sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program for
    Find all subsequences with given sum and length
*/

class Subsequence
{
	public:
		// Display result
		void show(int output[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << "  " << output[i];
			}
			cout << "\n";
		}
	// Find and print the all subsequences of given sum and length
	void subsequenceSum(int arr[], int output[], int i, int j, int n, int k, int sum, int result)
	{
		if (j == k && sum == result)
		{
			// Get subsequence with given sum and length
			this->show(output, k);
		}
		// Stop execution process
		if (i == n || j >= k)
		{
			return;
		}
		// Get element
		output[j] = arr[i];
		this->subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr[i]);
		this->subsequenceSum(arr, output, i + 1, j, n, k, sum, result);
	}
	// Handles the request of find all sequences with given sum and length k
	void findSubsequence(int arr[], int n, int k, int sum)
	{
		if (k <= 0 || n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		int result[k];
		cout << "\n Subsequence Sum : " << sum;
		cout << "\n Length : " << k << "\n";
		this->subsequenceSum(arr, result, 0, 0, n, k, sum, 0);
	}
};
int main()
{
	Subsequence task = Subsequence();
	int arr[] = {
		1 , 9 , 8 , -4 , 2 , 3 , 5 , 6
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 3;
	int sum = 10;
	// Test case
	task.findSubsequence(arr, n, k, sum);
	return 0;
}

Output

 Subsequence Sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5
// Include namespace system
using System;
/*
    C# Program for
    Find all subsequences with given sum and length
*/
public class Subsequence
{
	// Display result
	public void show(int[] output, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write("  " + output[i]);
		}
		Console.Write("\n");
	}
	// Find and print the all subsequences of given sum and length
	public void subsequenceSum(int[] arr, int[] output, int i, int j, int n, int k, int sum, int result)
	{
		if (j == k && sum == result)
		{
			// Get subsequence with given sum and length
			show(output, k);
		}
		// Stop execution process
		if (i == n || j >= k)
		{
			return;
		}
		// Get element
		output[j] = arr[i];
		subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr[i]);
		subsequenceSum(arr, output, i + 1, j, n, k, sum, result);
	}
	// Handles the request of find all sequences with given sum and length k
	public void findSubsequence(int[] arr, int n, int k, int sum)
	{
		if (k <= 0 || n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		int[] result = new int[k];
		Console.Write("\n Subsequence Sum : " + sum);
		Console.Write("\n Length : " + k + "\n");
		subsequenceSum(arr, result, 0, 0, n, k, sum, 0);
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		int[] arr = {
			1 , 9 , 8 , -4 , 2 , 3 , 5 , 6
		};
		int n = arr.Length;
		int k = 3;
		int sum = 10;
		// Test case
		task.findSubsequence(arr, n, k, sum);
	}
}

Output

 Subsequence Sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5
<?php
/*
    Php Program for
    Find all subsequences with given sum and length
*/
class Subsequence
{
	// Display result
	public	function show( & $output, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo "  ". $output[$i];
		}
		echo "\n";
	}
	// Find and print the all subsequences of given sum and length
	public	function subsequenceSum( & $arr, & $output, $i, $j, $n, $k, $sum, $result)
	{
		if ($j == $k && $sum == $result)
		{
			// Get subsequence with given sum and length
			$this->show($output, $k);
		}
		// Stop execution process
		if ($i == $n || $j >= $k)
		{
			return;
		}
		// Get element
		$output[$j] = $arr[$i];
		$this->subsequenceSum($arr, $output, $i + 1, $j + 1, $n, $k, $sum, $result + $arr[$i]);
		$this->subsequenceSum($arr, $output, $i + 1, $j, $n, $k, $sum, $result);
	}
	// Handles the request of find all sequences with given sum and length k
	public	function findSubsequence( & $arr, $n, $k, $sum)
	{
		if ($k <= 0 || $n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		$result = array_fill(0, $k, 0);
		echo "\n Subsequence Sum : ". $sum;
		echo "\n Length : ". $k ."\n";
		$this->subsequenceSum($arr, $result, 0, 0, $n, $k, $sum, 0);
	}
}

function main()
{
	$task = new Subsequence();
	$arr = array(1, 9, 8, -4, 2, 3, 5, 6);
	$n = count($arr);
	$k = 3;
	$sum = 10;
	// Test case
	$task->findSubsequence($arr, $n, $k, $sum);
}
main();

Output

 Subsequence Sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5
/*
    Node Js Program for
    Find all subsequences with given sum and length
*/
class Subsequence
{
	// Display result
	show(output, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write("  " + output[i]);
		}
		process.stdout.write("\n");
	}
	// Find and print the all subsequences of given sum and length
	subsequenceSum(arr, output, i, j, n, k, sum, result)
	{
		if (j == k && sum == result)
		{
			// Get subsequence with given sum and length
			this.show(output, k);
		}
		// Stop execution process
		if (i == n || j >= k)
		{
			return;
		}
		// Get element
		output[j] = arr[i];
		this.subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr[i]);
		this.subsequenceSum(arr, output, i + 1, j, n, k, sum, result);
	}
	// Handles the request of find all sequences with given sum and length k
	findSubsequence(arr, n, k, sum)
	{
		if (k <= 0 || n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		var result = Array(k).fill(0);
		process.stdout.write("\n Subsequence Sum : " + sum);
		process.stdout.write("\n Length : " + k + "\n");
		this.subsequenceSum(arr, result, 0, 0, n, k, sum, 0);
	}
}

function main()
{
	var task = new Subsequence();
	var arr = [1, 9, 8, -4, 2, 3, 5, 6];
	var n = arr.length;
	var k = 3;
	var sum = 10;
	// Test case
	task.findSubsequence(arr, n, k, sum);
}
main();

Output

 Subsequence Sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5
#  Python 3 Program for
#  Find all subsequences with given sum and length

class Subsequence :
	#  Display result
	def show(self, output, n) :
		i = 0
		while (i < n) :
			print("  ", output[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Find and print the all subsequences of given sum and length
	def subsequenceSum(self, arr, output, i, j, n, k, sum, result) :
		if (j == k and sum == result) :
			#  Get subsequence with given sum and length
			self.show(output, k)
		
		#  Stop execution process
		if (i == n or j >= k) :
			return
		
		#  Get element
		output[j] = arr[i]
		self.subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr[i])
		self.subsequenceSum(arr, output, i + 1, j, n, k, sum, result)
	
	#  Handles the request of find all sequences with given sum and length k
	def findSubsequence(self, arr, n, k, sum) :
		if (k <= 0 or n <= 0) :
			return
		
		#  Used to collect Subsequence element
		result = [0] * (k)
		print("\n Subsequence Sum : ", sum, end = "")
		print("\n Length : ", k )
		self.subsequenceSum(arr, result, 0, 0, n, k, sum, 0)
	

def main() :
	task = Subsequence()
	arr = [1, 9, 8, -4, 2, 3, 5, 6]
	n = len(arr)
	k = 3
	sum = 10
	#  Test case
	task.findSubsequence(arr, n, k, sum)

if __name__ == "__main__": main()

Output

 Subsequence Sum :  10
 Length :  3
   1   3   6
   9   -4   5
   8   -4   6
   2   3   5
#  Ruby Program for
#  Find all subsequences with given sum and length

class Subsequence 
	#  Display result
	def show(output, n) 
		i = 0
		while (i < n) 
			print("  ", output[i])
			i += 1
		end

		print("\n")
	end

	#  Find and print the all subsequences of given sum and length
	def subsequenceSum(arr, output, i, j, n, k, sum, result) 
		if (j == k && sum == result) 
			#  Get subsequence with given sum and length
			self.show(output, k)
		end

		#  Stop execution process
		if (i == n || j >= k) 
			return
		end

		#  Get element
		output[j] = arr[i]
		self.subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr[i])
		self.subsequenceSum(arr, output, i + 1, j, n, k, sum, result)
	end

	#  Handles the request of find all sequences with given sum and length k
	def findSubsequence(arr, n, k, sum) 
		if (k <= 0 || n <= 0) 
			return
		end

		#  Used to collect Subsequence element
		result = Array.new(k) {0}
		print("\n Subsequence Sum : ", sum)
		print("\n Length : ", k ,"\n")
		self.subsequenceSum(arr, result, 0, 0, n, k, sum, 0)
	end

end

def main() 
	task = Subsequence.new()
	arr = [1, 9, 8, -4, 2, 3, 5, 6]
	n = arr.length
	k = 3
	sum = 10
	#  Test case
	task.findSubsequence(arr, n, k, sum)
end

main()

Output

 Subsequence Sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5
/*
    Scala Program for
    Find all subsequences with given sum and length
*/
class Subsequence
{
	// Display result
	def show(output: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print("  " + output(i));
			i += 1;
		}
		print("\n");
	}
	// Find and print the all subsequences of given sum and length
	def subsequenceSum(arr: Array[Int], output: Array[Int], i: Int, j: Int, n: Int, k: Int, sum: Int, result: Int): Unit = {
		if (j == k && sum == result)
		{
			// Get subsequence with given sum and length
			this.show(output, k);
		}
		// Stop execution process
		if (i == n || j >= k)
		{
			return;
		}
		// Get element
		output(j) = arr(i);
		this.subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr(i));
		this.subsequenceSum(arr, output, i + 1, j, n, k, sum, result);
	}
	// Handles the request of find all sequences with given sum and length k
	def findSubsequence(arr: Array[Int], n: Int, k: Int, sum: Int): Unit = {
		if (k <= 0 || n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		var result: Array[Int] = Array.fill[Int](k)(0);
		print("\n Subsequence Sum : " + sum);
		print("\n Length : " + k + "\n");
		this.subsequenceSum(arr, result, 0, 0, n, k, sum, 0);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		var arr: Array[Int] = Array(1, 9, 8, -4, 2, 3, 5, 6);
		var n: Int = arr.length;
		var k: Int = 3;
		var sum: Int = 10;
		// Test case
		task.findSubsequence(arr, n, k, sum);
	}
}

Output

 Subsequence Sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5
/*
    Swift 4 Program for
    Find all subsequences with given sum and length
*/
class Subsequence
{
	// Display result
	func show(_ output: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  ", output[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Find and print the all subsequences of given sum and length
	func subsequenceSum(_ arr: [Int], _ output: inout[Int], _ i: Int, _ j: Int, _ n: Int, _ k: Int, _ sum: Int, _ result: Int)
	{
		if (j == k && sum == result)
		{
			// Get subsequence with given sum and length
			self.show(output, k);
		}
		// Stop execution process
		if (i == n || j >= k)
		{
			return;
		}
		// Get element
		output[j] = arr[i];
		self.subsequenceSum(arr, &output, i + 1, j + 1, n, k, sum, result + arr[i]);
		self.subsequenceSum(arr, &output, i + 1, j, n, k, sum, result);
	}
	// Handles the request of find all sequences with given sum and length k
	func findSubsequence(_ arr: [Int], _ n: Int, _ k: Int, _ sum: Int)
	{
		if (k <= 0 || n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		var result: [Int] = Array(repeating: 0, count: k);
		print("\n Subsequence Sum : ", sum, terminator: "");
		print("\n Length : ", k );
		self.subsequenceSum(arr, &result, 0, 0, n, k, sum, 0);
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	let arr: [Int] = [1, 9, 8, -4, 2, 3, 5, 6];
	let n: Int = arr.count;
	let k: Int = 3;
	let sum: Int = 10;
	// Test case
	task.findSubsequence(arr, n, k, sum);
}
main();

Output

 Subsequence Sum :  10
 Length :  3
   1   3   6
   9   -4   5
   8   -4   6
   2   3   5
/*
    Kotlin Program for
    Find all subsequences with given sum and length
*/
class Subsequence
{
	// Display result
	fun show(output: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  " + output[i]);
			i += 1;
		}
		print("\n");
	}
	// Find and print the all subsequences of given sum and length
	fun subsequenceSum(arr: Array <Int> , output: Array <Int> , i: Int, j: Int, n: Int, k: Int, sum: Int, result: Int): Unit
	{
		if (j == k && sum == result)
		{
			// Get subsequence with given sum and length
			this.show(output, k);
		}
		// Stop execution process
		if (i == n || j >= k)
		{
			return;
		}
		// Get element
		output[j] = arr[i];
		this.subsequenceSum(arr, output, i + 1, j + 1, n, k, sum, result + arr[i]);
		this.subsequenceSum(arr, output, i + 1, j, n, k, sum, result);
	}
	// Handles the request of find all sequences with given sum and length k
	fun findSubsequence(arr: Array < Int > , n: Int, k: Int, sum: Int): Unit
	{
		if (k <= 0 || n <= 0)
		{
			return;
		}
		// Used to collect Subsequence element
		var result: Array < Int > = Array(k)
		{
			0
		};
		print("\n Subsequence Sum : " + sum);
		print("\n Length : " + k + "\n");
		this.subsequenceSum(arr, result, 0, 0, n, k, sum, 0);
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Subsequence = Subsequence();
	var arr: Array < Int > = arrayOf(1, 9, 8, -4, 2, 3, 5, 6);
	var n: Int = arr.count();
	var k: Int = 3;
	var sum: Int = 10;
	// Test case
	task.findSubsequence(arr, n, k, sum);
}

Output

 Subsequence Sum : 10
 Length : 3
  1  3  6
  9  -4  5
  8  -4  6
  2  3  5

Result and Output Explanation

For the given example array [1, 9, 8, -4, 2, 3, 5, 6], we want to find all subsequences of length 3 with a sum of 10. The resulting output is as follows:

Subsequence sum: 10
Length: 3
1 3 6
9 -4 5
8 -4 6
2 3 5

The output represents the subsequences that satisfy the given conditions. Each line corresponds to a subsequence, where the numbers are separated by spaces. For example, the first line "1 3 6" represents a subsequence with elements [1, 3, 6] that has a sum of 10 and length 3.

Time Complexity

The time complexity of the solution depends on the number of subsequences that satisfy the conditions. Since we need to generate all possible subsequences, the time complexity is exponential. Specifically, it can be represented as O(2^n), where n is the length of the input array.

This is because for each element in the array, we have two choices: either include it in the subsequence or exclude it. As a result, the number of recursive calls grows exponentially with the input size.

Finally

In this article, we discussed the problem of finding all subsequences with a given sum and length. We provided a step-by-step explanation of the problem, including a suitable example. We presented an algorithm and its pseudocode to solve the problem using a recursive approach. Furthermore, we explained the resulting output and discussed the time complexity of the solution.

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