Print all Subsequences of an Array

Given an array of integers, Print all possible subsequences of that array.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. (Definition from Wikipedia).

If the input array is { 1, 2, 3, 4, 5, 6, 7, 8}, then following are the subsequences:

{1, 3, 5}
{1, 8}
{1, 2, 3}
{}
{1, 2, 3, 4, 5, ,6 7, 8}

But following are not subsequences:

{1, 5, 3} // The Order of elements is not same as Original array
{1, 9} // 9 is not part of original array

Solution:

The order of elements in the main array and subsequence remains the same, so essentially, at each element, we have two choices, either to include the element or exclude it. By following these choices at each element, we can generate all the subsequences.

If the input array is {1} (with only one element). Then two possible subsequences are:

If the array is {1, 2}, then we have to make the decision (Include / Exclude) for both the elements.

Similarly, we can extend the solution for n elements.

Java Code:

public class Temp {
   public static void printArray(int[] a, int n)
   {
	   System.out.println();
      for(int i=0; i= arr.length)
      {
         printArray(ss, j); // PRINT FIRST j ELEMENTS OF ss
         return;
      }

      // INCLUDING THE CURRENT ELEMENT OF arr
      ss[j] = arr[i];
      printAllSubSequences(arr, i+1, ss, j+1);

      // EXCLUDING THE CURRENT ELEMENT OF arr
      printAllSubSequences(arr, i+1, ss, j);
   }
   
   public static void main(String[] args)  
   {  
      int[] a = {1, 2, 3, 4};

      // TEMP ARRAY TO HOLD SubSequence. 
      // This can go in the wrapper function
      int[] ss = new int[4]; 
      printAllSubSequences(a, 0, ss, 0);
   }		
}