Generate All Subsets

Given a list of unique integers, generate all possible subsets (the power set) of the list. The subsets must satisfy the following conditions:

• Subsets are sorted in ascending order by their length.
• For subsets of the same length, they are sorted in lexicographical order (based on the integer values).
• No duplicate subsets should be included.

The algorithm can be formulated using backtracking. In particular, if we denote the list as \(A = [a_1, a_2, \dots, a_n]\), then every subset \(S\) with \(S \subseteq A\) must be output in the order defined above. The sorting order can be expressed as:

\[ \text{order}(S) = \Big( |S|, \; S \Big), \]

Input will be provided from standard input (stdin) and the result should be printed to standard output (stdout). Each subset must be printed on a new line, formatted with square brackets. For a non-empty subset, elements should be separated by a single space, for example: [1 2] (and for an empty subset, print []).

inputFormat

The first line contains an integer \(n\) indicating the number of elements in the list. The second line contains \(n\) space-separated integers.

Example:

3
1 2 3

outputFormat

Print all subsets of the given list in the sorted order specified in the description. Each subset should be printed on a new line. Every subset must be enclosed within square brackets. For a non-empty subset, print the integers separated by a single space. For an empty subset, print [].

For the example input, the output should be:

[]
[1]
[2]
[3]
[1 2]
[1 3]
[2 3]
[1 2 3]

## sample

3
1 2 3

[]
[1]
[2]
[3]
[1 2]
[1 3]
[2 3]
[1 2 3]

</p>