**Objective**: 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 Generate 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:**

**Output:**

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

Much simpler code

public class ArraySubSequences {

public static void main(String[] args) {

int[] a = {1,2,3};

printSubSequences(a, 0, new ArrayList(), ” “);

}

static void printSubSequences(int[] arr, int start, List chosen, String space) {

if(start > arr.length) {

return;

}

else {

for (int i = start; i < arr.length; i++) {

//choose

chosen.add(arr[i]);

System.out.println(space + chosen);

//explore

printSubSequences(arr, i + 1, chosen, space + " ");

//un-choose

chosen.remove(chosen.size() – 1);

}

}

}

}