Generate All Subsets of a Set Using Bitmasking

Given an array of N distinct integers, generate all 2^N subsets (the power set) using bitmasking: each integer mask from 0 to 2^N - 1 represents one subset, where bit i of mask being set means the i-th array element is included. Print the subsets in increasing order of their mask value, one per line, listing each subset's elements space-separated in their original array order; print an empty line for the empty subset (mask = 0).

Input: The first line contains the integer N. The second line contains N space-separated integers, the array elements. Output: 2^N lines: the subset corresponding to mask 0, then mask 1, and so on up to mask 2^N - 1, each printed as its elements space-separated (an empty line for the empty subset).

1 <= N <= 16; -1000 <= arr[i] <= 1000

The small constraint here (N <= 16, so at most 65536 subsets) is a strong signal that this exponential-but-bounded enumeration is exactly the INTENDED approach, not something to optimize away.

Generate every possible subset of a set of N elements, using binary numbers from 0 to 2^N-1 to represent each subset. Brute force: Generate subsets recursively via explicit include/exclude branching at each element - this also works and produces the same subsets, but bitmasking offers a cleaner, purely iterative way to enumerate them in a fixed, predictable numeric order. Optimised: Since there's a natural ONE-TO-ONE correspondence between N-bit binary numbers and subsets of an N-element set, simply iterating integers from 0 to 2^N-1 and reading off which bits are set directly enumerates every subset - no recursion, no explicit branching logic needed, just bit extraction.

1. Recognize that each integer mask from 0 to 2^N - 1 corresponds to exactly ONE subset: bit i of mask being set means element i is included. 2. Iterate masks in increasing order; for each mask, scan bits 0 through N-1, collecting the elements whose corresponding bit is set, in original array order. 3. Print each subset's elements space-separated, including a blank line for mask=0 (the empty subset).

Time: O(N * 2^N) - there are 2^N subsets, and generating each one takes O(N) to scan all bit positions. Space: O(N) per subset generated (or O(N * 2^N) if all subsets are stored at once).

N = 1 produces exactly two subsets: the empty one and the single-element one; array elements may be negative or zero.

Be ready to explain the direct correspondence between bitmasks and subsets clearly - this technique generalizes to many other 'enumerate all subsets/combinations' problems (subset sum, subset XOR, and more) as a clean, iterative alternative to recursive backtracking.