Generate All Subsets

Given an array of distinct integers, generate all possible subsets (the power set) using a backtracking algorithm. Remember to include the empty subset and the subset containing all elements.

You must read the input from standard input (stdin) and print the output to standard output (stdout). The output should begin with a single integer that represents the total number of subsets, followed by each subset on a new line. For each subset, print the elements in the order they appear separated by a single space. If a subset is empty, simply output an empty line.

inputFormat

The first line contains an integer \(n\) indicating the number of elements in the array. If \(n > 0\), the second line contains \(n\) space-separated integers.

outputFormat

The first line should contain an integer representing the total number of subsets. Each of the following lines should represent one subset with its elements separated by a single space. For the empty subset, output an empty line.

3
1 2 3

8
1
1 2
1 2 3
1 3
2
2 3
3