Power set of a set
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): [[]]
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;}