Subsets

The array has distinct integers. Print all its subsets (the power set), including the empty one.

Input:

• line 1: n
• line 2: n distinct integers

Output: one subset per line in the form [a b c] (the empty subset is []). So there is exactly one correct output:

• list the numbers inside each subset in increasing order;
• list the subsets in lexicographic order — compare them number by number, and a subset that is a prefix of another comes first ([], [1], [1 2], [1 2 3], [1 3], [2], …).

Constraints: 1 ≤ n ≤ 12, −100 ≤ value ≤ 100.

Think about it: sort first. Then the classic backtracking — "print the current subset, then for every later element: add it, recurse, remove it" — produces exactly this order.