**Problem Statement:** Given a string, find all the possible subsequences of the string.

**Examples:**

Example 1:Input:str = "abc"Output:a ab abc ac b bc cExplanation:Printing all the 7 subsequence for the string "abc".Example 2:Input:str = "aa"Output:a a aaExplanation:Printing all the 3 subsequences for the string "aa"

**Solution**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1: Using bit manipulation**

**Approach**: Prerequisites: To check whether the ith bit is set or not.If n&(1<<i) != 0,then the ith bit is set.

First, write down all the numbers from 0 to 2^(n)-1 and their bit representation.0 means I am not picking the character in my subsequence, and 1 means I am picking the character.

Basically, we traverse from 0 to 2^(n)-1 and check for every number if their bit is set or not. If the bit is set add that character to your subsequence.

**Code:**

## C++ Code

```
#include<bits/stdc++.h>
using namespace std;
vector<string> AllPossibleStrings(string s) {
int n = s.length();
vector<string>ans;
for (int num = 0; num < (1 << n); num++) {
string sub = "";
for (int i = 0; i < n; i++) {
//check if the ith bit is set or not
if (num & (1 << i)) {
sub += s[i];
}
}
if (sub.length() > 0) {
ans.push_back(sub);
}
}
sort(ans.begin(), ans.end());
return ans;
}
int main()
{
string s="abc";
vector<string>ans = AllPossibleStrings(s);
//printint all the subsequence.
cout<<"All possible subsequences are "<<endl;
for (auto it : ans) {
cout << it << " ";
}
}
```

**Output:**

All possible subsequences are

a ab abc ac b bc c

**Time Complexity**: O(2^n * n)** **

**Reason:** O(2^n) for the outer for loop and O(n) for the inner for loop.

**Space Complexity:** O(1)

## Java Code

```
import java.util.*;
class TUF{
static ArrayList<String> AllPossibleStrings(String s) {
int n = s.length();
ArrayList<String>ans=new ArrayList<>();
for (int num = 0; num < (1 << n); num++) {
String sub = "";
for (int i = 0; i < n; i++) {
//check if the ith bit is set or not
if ((num & (1 << i))!=0) {
sub += s.charAt(i);
}
}
if (sub.length() > 0) {
ans.add(sub);
}
}
Collections.sort(ans);
return ans;
}
public static void main(String args[])
{
String s="abc";
ArrayList<String>ans = AllPossibleStrings(s);
//printint all the subsequence.
System.out.println("All possible subsequences are ");
for (String it : ans) {
System.out.print( it+" ");
}
}
}
```

**Output:**

All possible subsequences are

a ab abc ac b bc c

**Time Complexity**: O(2^n * n)** **

**Reason:** O(2^n) for the outer for loop and O(n) for the inner for loop.

**Space Complexity:** O(1)

**Solution 2: Using recursion(Backtracking)**

**Intuition: **Since we are generating subsets two cases will be possible, either you can pick the character or you cannot pick the character and move to the next character.

**Approach:**

- Maintain a temp string (say f),which is empty initally.
- Now you have two options,either you can pick the character or not pick the character and move to the next index.
- Firstly we pick the character at ith index and then move to the next index.(f + s[i])
- If the base condition is hit,i.e i==s.length() ,then we print the temp string and return.
- Now while backtracking we have to pop the last character since now we have to implement the non-pick condition and then move to next index.

**Code:**

## C++ Code

```
#include<bits/stdc++.h>
using namespace std;
void solve(int i, string s, string &f) {
if (i == s.length()) {
cout << f << " ";
return;
}
//picking
f = f + s[i];
solve(i + 1, s, f);
//poping out while backtracking
f.pop_back();
solve(i + 1, s, f);
}
int main() {
string s = "abc";
string f = "";
cout<<"All possible subsequences are: "<<endl;
solve(0, s, f);
}
```

**Output:**

All possible subsequences are:

abc ab ac a bc b c

**Time Complexity:** O(2^n)

**Space Complexity: **O(n), recursion stack.

## Java Code

```
import java.util.*;
class TUF{
static void solve(int i, String s, String f) {
if (i == s.length()) {
System.out.print(f+" ");
return;
}
//picking
//f = f + s.charAt(i);
solve(i + 1, s, f+s.charAt(i));
//poping out while backtracking
//f.pop_back();
solve(i + 1, s, f);
}
public static void main(String args[]) {
String s = "abc";
String f = "";
System.out.println("All possible subsequences are: ");
solve(0, s, f);
}
}
```

**Output:**

All possible subsequences are:

abc ab ac a bc b c

**Time Complexity:** O(2^n)

**Space Complexity: **O(n), recursion stack.

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article