Power Set Using Bit Manipulation

Power Set Using Bit Manipulation

Generate the power set of an array using bitmasking instead of recursion.

Input format

The first line contains N (1 ≤ N ≤ 10). The second line contains N integers.

Output format

Print every non-empty subset on its own line, iterating masks from 1 to 2^N − 1; bit i of the mask (least significant bit = index 0) selects a[i]. Elements of a subset are printed in index order, space-separated.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

3
1 2 3

1
2
1 2
3
1 3
2 3
1 2 3

1
5

5