# Generating all possible Subsequences using Recursion

## Generating all possible Subsequences using Recursion

Given an array. The task is to generate and print all of the possible subsequences of the given array using recursion.

Examples:

```Input : [1, 2, 3]
Output : [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]

Input : [1, 2]
Output : [2], [1], [1, 2]
```

Approach: For every element in the array, there are two choices, either to include it in the subsequence or not include it. Apply this for every element in the array starting from index 0 until we reach the last index. Print the subsequence once the last index is reached.

Below diagram shows the recursion tree for array, arr[] = {1, 2}.

Below is the implementation of the above approach.

 `// C++ code to print all possible` `// subsequences for given array using` `// recursion` `#include ` `using` `namespace` `std;` `void` `printArray(vector<``int``> arr, ``int` `n)` `{` `    ``for` `(``int` `i = 0; i < n; i++)` `        ``cout << arr[i] << ``" "``;` `    ``cout << endl;` `}` `// Recursive function to print all` `// possible subsequences for given array` `void` `printSubsequences(vector<``int``> arr, ``int` `index,` `                       ``vector<``int``> subarr)` `{` `    ``// Print the subsequence when reach` `    ``// the leaf of recursion tree` `    ``if` `(index == arr.size())` `    ``{` `        ``int` `l = subarr.size();` `        ``// Condition to avoid printing` `        ``// empty subsequence` `        ``if` `(l != 0)` `            ``printArray(subarr, l);` `    ``}` `    ``else` `    ``{` `        ``// Subsequence without including` `        ``// the element at current index` `        ``printSubsequences(arr, index + 1, subarr);` `        ``subarr.push_back(arr[index]);` `        ``// Subsequence including the element` `        ``// at current index` `        ``printSubsequences(arr, index + 1, subarr);` `    ``}` `    ``return``;` `}` `// Driver Code` `int` `main()` `{` `    ``vector<``int``> arr{1, 2, 3};` `    ``vector<``int``> b;` `    ``printSubsequences(arr, 0, b);` `    ``return` `0;` `}` `// This code is contributed by` `// sanjeev2552`

Output:

```[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]```

Time Complexity:

Last Updated on March 1, 2022 by admin

## Python – Remove all values from a list present in other listPython – Remove all values from a list present in other list

Python | Remove all values from a list present in other list Sometimes we need

## Python PIL – ImageDraw.Draw.rectangle()Python PIL – ImageDraw.Draw.rectangle()

Python PIL | ImageDraw.Draw.rectangle() PIL is the Python Imaging Library which provides the python interpreter

## Randomly select n elements from list in PythonRandomly select n elements from list in Python

Randomly select n elements from list in Python In this article, we will discuss how

## Deploy Python Flask App on HerokuDeploy Python Flask App on Heroku

Deploy Python Flask App on Heroku Flask is a web application framework written in Python.

## Python program to get all unique combinations of two ListsPython program to get all unique combinations of two Lists

Python program to get all unique combinations of two Lists The combination is a mathematical

## How to compare two NumPy arrays?How to compare two NumPy arrays?

How to compare two NumPy arrays? This article focuses on the comparison done using NumPy

## Remove all the occurrences of an element from a list in PythonRemove all the occurrences of an element from a list in Python

Remove all the occurrences of an element from a list in Python The task is

## Python | Generate random numbers within a given range and store in a listPython | Generate random numbers within a given range and store in a list

Python | Generate random numbers within a given range and store in a list Given