Skip to main content

Find all subsequences with given sum and length

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
Last updated on by Kalkicode




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