Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. A subset of n elements can be described by n bits: bit i says whether a[i] is included.
  2. 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