Unique Subsets Generation

Given an integer array that may contain duplicates, your task is to generate all possible unique subsets of the array. A subset is defined as a sequence of elements selected from the array. Two subsets are considered identical if they contain the same elements in the same order.

For instance, if the input array is sorted as ( [a_1, a_2, \dots, a_n] ), then the total number of subsets in the absence of duplicates is (2^n). However, when duplicates are present, only unique subsets should be returned. To ensure consistency, after generating all subsets, sort them first by their size and then in lexicographical order.

Note: The output for an empty subset should be an empty line, and each subset must be printed on a separate line.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers. If ( n = 0 ), the second line will be empty.

outputFormat

Output all unique subsets to standard output (stdout). Each subset should appear on a new line with its elements separated by a single space. For an empty subset, print an empty line.## sample

3
1 2 2

1
2
1 2
2 2
1 2 2