Unique Subsets

Given an array of integers (which may contain duplicates), your task is to compute and output all unique subsets of the array. First, sort the array in non-decreasing order and then use depth-first search (DFS) to generate all possible subsets. Duplicate subsets are not allowed. The empty subset should be represented as an empty line.

In formal terms, if the input array is (A), you need to output every subset (S) such that each (S) is unique. The DFS generation ensures that duplicates are skipped by checking if the current element is the same as the previous one (after the first occurrence).

inputFormat

Input is read from standard input (stdin). The first line contains a non-negative integer (n) representing the number of elements in the array. If (n > 0), the second line contains (n) space-separated integers.

outputFormat

Output to standard output (stdout) each unique subset on a separate line. For each subset, output the integers separated by a single space. For the empty subset, output an empty line.## sample

3
1 2 2

1
1 2
1 2 2
2
2 2