# Print all sub sequences of a given array

Objec­tive:  Given an array write an algorithm to print all the possible sub subsequences.

Example:

```int [] a = {1, 2, 3};
Output: Possible sub sequences –
{Empty}, {1}, {2}, {3}, {1, 2} ,{1,3}, {2, 3}, {1, 2, 3}
```

Approach:

• The approach will be similar to as discussed here Gen­er­ate All Strings of n bits
• If we consider n= 3(same as the array size) then all possible combinations are [0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] [0, 1, 1] [1, 1, 1].
• So from the above combinations, wherever the bit is set to 1, place an array element at the position and wherever the bit is set to 0, ignore the array element.
• The above step will give the desired result.
• See the code below for better understanding.

Time Complexity: O(2^n)

Complete Code:

 public class PrintArraySubSequences { public void printAllSubSequences(int [] arrInput){ int [] temp = new int[arrInput.length]; int index = 0; solve(arrInput, index, temp); } private void solve(int [] arrInput, int index, int [] temp){ if(index==arrInput.length){ print(arrInput,temp); return; } //set the current index bit and solve it recursively temp[index] = 1; solve(arrInput,index+1,temp); //unset the current index bit and solve it recursively temp[index] = 0; solve(arrInput,index+1,temp); } private void print(int [] arrInput, int [] temp){ String result = ""; for (int i = 0; i

Output:

```1 2 3
1 2
1 3
1
2 3
2
3
{Empty Set}```