===== Prelude 1 to Backtracking -- Subsets ======

For this prelude, you are to use your skeleton file for doing backtracking and compute the subsets of N.

===== Input =====

Input consists of a sequence of non-negative integers, N (0 < N < 10), one per line.  

===== Output =====

For each input value, N, generate the subsets of the numbers 1..N.  Each subset should be on a line by itself, surrounded by { }, in the order shown below (which is the "natural" order when following the strategy outlined in class).  A single blank line should separate each test case.

===== Sample Input =====

<code>
3
4
</code>

===== Sample Output =====

<code>
{ 1 2 3 }
{ 1 2 }
{ 1 3 }
{ 1 }
{ 2 3 }
{ 2 }
{ 3 }
{ }

{ 1 2 3 4 }
{ 1 2 3 }
{ 1 2 4 }
{ 1 2 }
{ 1 3 4 }
{ 1 3 }
{ 1 4 }
{ 1 }
{ 2 3 4 }
{ 2 3 }
{ 2 4 }
{ 2 }
{ 3 4 }
{ 3 }
{ 4 }
{ }
</code>