Power set of a set

Easy

Problem

Return all 2^n subsets of a set of distinct elements, including the empty set.

Example 1

Input:  [a, b, c]
Output: [], [a], [b], [c], [a,b], [a,c], [b,c], [a,b,c]

Also asked as: Power Set

Test cases

Case 1

Input:    ["a","b","c"]
Expected (any order): [[],["a"],["b"],["c"],["a","b"],["a","c"],["b","c"],["a","b","c"]]

Case 2

Input:    [1,2]
Expected (any order): [[],[1],[2],[1,2]]

Case 3

Input:    [1]
Expected (any order): [[],[1]]

Case 4

Input:    []
Expected (any order): [[]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Bitmask enumeration

Time O(2ⁿ · n)Space O(1) extra

Every subset ↔ a number 0..2ⁿ−1; bit j set means element j is included.

function powerSet(arr) {
const n = arr.length, res = [];
for (let mask = 0; mask < (1 << n); mask++) {
const subset = [];
for (let j = 0; j < n; j++) if (mask & (1 << j)) subset.push(arr[j]);
res.push(subset);
}
return res;
}