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)
{
int[] arr = {
1 , 9 , 8 , -4 , 2 , 3 , 5 , 6
};
int n = arr.length;
int k = 3;
int sum = 10;
// Test case
}
}``````

#### 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()
{
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
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)
{
int[] arr = {
1 , 9 , 8 , -4 , 2 , 3 , 5 , 6
};
int n = arr.Length;
int k = 3;
int sum = 10;
// Test case
}
}``````

#### 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()
{
\$arr = array(1, 9, 8, -4, 2, 3, 5, 6);
\$n = count(\$arr);
\$k = 3;
\$sum = 10;
// Test case
}
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 arr = [1, 9, 8, -4, 2, 3, 5, 6];
var n = arr.length;
var k = 3;
var sum = 10;
// Test case
}
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() :
arr = [1, 9, 8, -4, 2, 3, 5, 6]
n = len(arr)
k = 3
sum = 10
#  Test case

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()
arr = [1, 9, 8, -4, 2, 3, 5, 6]
n = arr.length
k = 3
sum = 10
#  Test case
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
}
}``````

#### 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 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
}
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 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
}``````

#### 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.

Categories
Relative Post