Practice › Bit Manipulation
Power Set Using Bitmasks
Medium · Bit Manipulation · Asked at Amazon, Microsoft, Meta
Print every non-empty subset of the array using bitmasks: for mask from 1 to 2^n − 1, print the elements a[i] whose bit i is set in mask, in index order, one subset per line.
Input
First line: n. Second line: n space-separated integers.
Output
2^n − 1 lines, one subset each.
Constraints
- 1 ≤ n ≤ 12
Bit i of mask decides whether a[i] is in the subset: (mask >> i) & 1.
Example 1
Input
3 1 2 3
Output
1 2 1 2 3 1 3 2 3 1 2 3
Example 2
Input
1 5
Output
5
Hints
- A subset of n elements can be described by n bits: bit i says whether a[i] is included.
- Loop mask from 1 to 2^n − 1 and print a[i] for every i with (mask >> i) & 1.
Approach
Every integer mask in [0, 2^n) is a distinct subset, and every subset appears once. Skipping mask = 0 leaves out the empty set. For each mask, scan the n bits in index order and collect the chosen elements. Duplicated values are fine — subsets are defined by positions here.
Complexity: O(2^n · n) time · O(n) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
string out;
for (int mask = 1; mask < (1 << n); mask++) {
bool first = true;
for (int i = 0; i < n; i++)
if ((mask >> i) & 1) {
out += (first ? "" : " ") + to_string(a[i]);
first = false;
}
out += "\n";
}
cout << out;
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
out = []
for mask in range(1, 1 << n):
out.append(" ".join(str(a[i]) for i in range(n) if (mask >> i) & 1))
print("\n".join(out))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
StringBuilder sb = new StringBuilder();
for (int mask = 1; mask < (1 << n); mask++) {
boolean first = true;
for (int i = 0; i < n; i++)
if (((mask >> i) & 1) == 1) {
sb.append(first ? "" : " ").append(a[i]);
first = false;
}
sb.append('\n');
}
System.out.print(sb);
}
}Solve Power Set Using Bitmasks online · All practice problems