SimuVedaAlgorithms Lab Open in the lab

Bit manipulation / Intermediate

Subsets with a Bitmask Visualizer

Count mask from 0 to 2ⁿ − 1. Bit i of the mask says whether value i is in the subset. Counting in binary therefore lists every subset exactly once.

Start the Subsets with a Bitmask simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n·2ⁿ)
Average timeO(n·2ⁿ)
Worst timeO(n·2ⁿ)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. 3 values, so masks run from 0 to 2^3 − 1 = 7.
  2. mask 0 is 000 in binary. Column i shows bit i, which decides nums[i], so take [].
  3. mask 1 is 001 in binary. Column i shows bit i, which decides nums[i], so take [1].
  4. mask 2 is 010 in binary. Column i shows bit i, which decides nums[i], so take [2].
  5. mask 3 is 011 in binary. Column i shows bit i, which decides nums[i], so take [1, 2].
  6. mask 4 is 100 in binary. Column i shows bit i, which decides nums[i], so take [3].
  7. mask 5 is 101 in binary. Column i shows bit i, which decides nums[i], so take [1, 3].
  8. mask 6 is 110 in binary. Column i shows bit i, which decides nums[i], so take [2, 3].
  9. mask 7 is 111 in binary. Column i shows bit i, which decides nums[i], so take [1, 2, 3].
  10. Done. 8 subsets from 8 masks.

Try it with your own input →

Subsets with a bitmask in Java, Python, C++, C and JavaScript

List<List<Integer>> subsets(int[] nums) {
  int n = nums.length;
  List<List<Integer>> result = new ArrayList<>();
  for (int mask = 0; mask < (1 << n); mask++) {
    List<Integer> subset = new ArrayList<>();
    for (int i = 0; i < n; i++)
      if ((mask & (1 << i)) != 0) subset.add(nums[i]);
    result.add(subset);
  }
  return result;
}
def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)
    return result
vector<vector<int>> subsets(const vector<int>& nums) {
  int n = nums.size();
  vector<vector<int>> result;
  for (int mask = 0; mask < (1 << n); mask++) {
    vector<int> subset;
    for (int i = 0; i < n; i++)
      if (mask & (1 << i)) subset.push_back(nums[i]);
    result.push_back(subset);
  }
  return result;
}
#include <stdio.h>

/* Prints every subset, one per line. */
void subsets(int nums[], int n) {
  for (int mask = 0; mask < (1 << n); mask++) {
    printf("{");
    for (int i = 0; i < n; i++)
      if (mask & (1 << i)) printf(" %d", nums[i]);
    printf(" }");
  }
}
function subsets(nums) {
  const n = nums.length;
  const result = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++)
      if (mask & (1 << i)) subset.push(nums[i]);
    result.push(subset);
  }
  return result;
}

In an interview

LeetCode 78, Subsets, solved without recursion. Bitmasks also drive bitmask DP such as 847 Shortest Path Visiting All Nodes.

Compare with the recursive Subsets in Backtracking: same 2ⁿ answers, no call stack. The check is (mask >> i) & 1, or mask & (1 << i).

More bit manipulation