Skip to content

Home

Calculate the powerset of a JavaScript array

The powerset of a set is the set of all its subsets. For example, the powerset of [1, 2] is [[], [1], [2], [1, 2]]. In order to generate the powerset of a set, we can use a simple algorithm that iterates over the elements of the set and combines them into an array containing all combinations.

For that purpose, we can use Array.prototype.reduce(), starting with an empty array ([[]]) and then combining each element with the existing combinations using Array.prototype.map(). For each element, we concatenate it with each existing combination and add the result to the array.

const powerset = arr =>
  arr.reduce((a, v) => a.concat(a.map(r => r.concat(v))), [[]]);

powerset([1, 2]); // [[], [1], [2], [1, 2]]
💬 Note

For a powerset to make sense, the input array should not contain any duplicate elements. If it does, the resulting powerset will contain duplicate subsets.

More like this

Start typing a keyphrase to see matching snippets.