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

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 <temp.length ; i++) { | |

if(temp[i]==1) | |

result += arrInput[i]+" "; | |

} | |

if(result=="") | |

result = "{Empty Set}"; | |

System.out.println(result); | |

} | |

public static void main(String[] args) { | |

int [] arrInput = {1, 2, 3}; | |

new PrintArraySubSequences().printAllSubSequences(arrInput); | |

} | |

} |

**Output:**

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