Finding all the subsets of a set

Its a very common problem usually asked in  programming interviews in which you've to print all the subsets of a set.
Its a problem which is recursive in nature.
Essentially for an element to be present in a subset there are 2 options:

1)It is present in the set

2)It is absent in the set.

This is the reason why a set of n numbers has 2^n subsets.(2 options per element)

Here is the pseudo-code(C++) to print all the subsets followed by an example explaining how the code works.
1)A[] is the array of numbers whose subsets you want to find out.
2) bool a[] is the array of booleans where a[i] tells whether the number A[i] is present in the set or not.

1 2 3 4 5 6 7 8 9 10

print(int A[],int low,int high) { if(low>high) { for(all entries i in bool a[] which are true) print(A[i]) } else {set a[low] to true //include the element in the subset  print(A,low+1,high) set a[low] to false//not including the element in the subset print(A,low+1,high) } }

So lets say I've an array of 4 elements which could be numbers or characters but all of them are unique else the subsets would get repeated..
Eg: subset{1,2,2}={ {1} , {2} , {2} , {1,2} , {1,2} , {2,2} , {1,2,2} , Null}

 A={1,2,3,4}

I make the call to above function for the array A with low=0,high=3

Below is the order of recursion.
When going left in the recursion tree below we set the a[low] to true and when going right we set a[low] to false.

                                             

1 2 3 4 5 6

print(0,3) print(1,3) print(1,3) print(2,3) print(2,3) print(2,3) print(2,3) print(3,3) print(3,3) print(3,3) print(3,3) print(3,3) print(3,3) print(3,3) print(3,3) / \ / \ / \ / \ / \ / \ / \ / \ 1234 123 124 12 134 13 14 1 234 23 24 2 34 3 4 null

The running time for this algorithm is exponential as can be seen from the recursion tree which is O(2^n).
or can be found out using the recurrence relation by substitution:
 T(n)=2*T(n-1)+c

Do remember that dynamic programming in this case can't be applied as the there are no overlapping sub-problems in this case since you've to print the power set.