How to find all subsets of a set in JavaScript? (Powerset of array)

Question

I need to get all possible subsets of an array.

Say I have this:

[1, 2, 3]

How do I get this?

[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]

I am interested in all subsets. For subsets of specific length, refer to the following questions:

• Finding subsets of size n: 1, 2
• Finding subsets of size > 1: 1

Answer 1

Here is one more very elegant solution with no loops or recursion, only using the map and reduce array native functions.

const getAllSubsets = 
      theArray => theArray.reduce(
        (subsets, value) => subsets.concat(
         subsets.map(set => [value,...set])
        ),
        [[]]
      );

console.log(getAllSubsets([1,2,3]));

Answer 2

We can solve this problem for a subset of the input array, starting from offset. Then we recurse back to get a complete solution.

Using a generator function allows us to iterate through subsets with constant memory usage:

// Generate all array subsets:
function* subsets(array, offset = 0) {
  while (offset < array.length) {
    let first = array[offset++];
    for (let subset of subsets(array, offset)) {
      subset.push(first);
      yield subset;
    }
  }
  yield [];
}

// Example:
for (let subset of subsets([1, 2, 3])) {
  console.log(subset); 
}

Runtime complexity is proportional to the number of solutions (2?) times the average length per solution (n/2) = O(n2?).

Answer 3

Another simple solution.

function getCombinations(array) {

    function fork(i, t) {
        if (i === array.length) {
            result.push(t);
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

var data = [1, 2, 3],
    result = getCombinations(data);
	
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 4

Simple solution without recursion:

function getAllSubsets(array) {
    const subsets = [[]];
    
    for (const el of array) {
        const last = subsets.length-1;
        for (let i = 0; i <= last; i++) {
            subsets.push( [...subsets[i], el] );
        }
    }
    
    return subsets;
}

---

How does it work?

If we have some subsets generated from input numbers and we want to add one more number to our input array, it means that we can take all already existing subsets and generate new ones by appending the new number to each of the existing.

---

Here is an example for [1, 2, 3]

• Start with an empty subset: []

• Create new subsets by adding "1" to each existing subset. It will be:[] [1]

• Create new subsets by adding "2" to each existing subset. It will be:[], [1] [2], [1, 2]

• Create new subsets by adding "3" to each existing subset. It will be: [], [1], [2], [1, 2] [3], [1, 3], [2, 3], [1, 2, 3]

Answer 5

You can easily generate the powerset from an array, using something like the following:

var arr = [1, 2, 3];

function generatePowerSet(array) {
  var result = [];
  result.push([]);

  for (var i = 1; i < (1 << array.length); i++) {
    var subset = [];
    for (var j = 0; j < array.length; j++)
      if (i & (1 << j))
        subset.push(array[j]);

    result.push(subset);
  }

  return result;
}

console.log(generatePowerSet(arr));

Throughout the main loop of the function, subsets are created and then pushed into the result array.

Answer 6

I set out to understand what is happening with the examples in this post. While the function generator example, bit-wise operator example, and the example use of the array map and reduce functions are very elegant and impressive, I found it tough to mentally visual what precisely was happening. I have 2 examples below that I believe are easy to visualize both a non-recursive and a recursive solution. I hope this helps others attempting to wrap their heads around the process of finding all subsets.

NON-RECURSIVE: For each value of the array clone all existing subsets (including the empty set) and add the new value to each of the clones, pushing the clones back to the results.

const PowerSet = array => {
  const result = [[]] // Starting with empty set
  
  for (let value of array) { // For each value of the array
     const length = result.length // Can't use result.length in loop since 
                                  // results length is increased in loop
      for (let i = 0; i < length; i++){
        let temp = result[i].slice(0) // Make a clone of the value at index i  
        temp.push(value) // Add current value to clone
        result.push(temp) // Add clone back to results array
      }
  }
  
  return result;
  }

  console.log(PowerSet([1,2,3]))

RECURSIVELY: Build the powerset by recursively pushing a combination of the current index value concatenated with an ever increasing prefix array of values.

const powerSetRecursive = (arr, prefix=[], set=[[]]) => {
  if(arr.length === 0) return// Base case, end recursion
  
  for (let i = 0; i < arr.length; i++) {
      set.push(prefix.concat(arr[i]))// If a prefix comes through, concatenate value
      powerSetRecursive(arr.slice(i + 1), prefix.concat(arr[i]), set)
      // Call function recursively removing values at or before i and adding  
      // value at i to prefix
  }
  return set
}

console.log(powerSetRecursive([1,2,3]))

Answer 7

function subSets(num){


/*
example given number : [1,3]
         []
 1:  copy   push 1
    []        [1]
  
 3: copy      push 3
    [] [1] [3] [1,3]


*/
  let result = [];

  result.push([]);

  for(let i=0; i < num.length;i++){

    let currentNum = num[i];
    let len = result.length;

    for(let j=0; j < len; j++){
      let cloneData = result[j].slice();
      cloneData.push(currentNum);
      result.push(cloneData)
    }
  }

  return result;
}

let test = [1,3];
console.log(subSets(test))//[ [], [ 1 ], [ 3 ], [ 1, 3 ] ]

Answer 8

let subsets = (n) => {

let result = [];
result.push([]);

n.forEach(a => {

  //array length
   let length = result.length;
    let i =0;

    while(i < length){

      let temp = result[i].slice(0);
      temp.push(a);

      result.push(temp);
      i++;

    }
})

return result;
}

Answer 9

Using flatMap and rest/spread, this can be fairly elegant:

const subsets = ([x, ...xs]) =>
  x == undefined
    ? [[]]
    : subsets (xs) .flatMap (ss => [ss, [x, ...ss]]) 

console .log (subsets ([1, 2, 3]))

.as-console-wrapper {max-height: 100% !important; top: 0}

This version does not return them in the requested order. Doing that seems slightly less elegant, and there's probably a better version:

const subset = (xs = []) => {
  if (xs.length == 0) {return [[]]}
  const ys = subset (xs .slice (0, -1))
  const x = xs .slice (-1) [0]
  return [... ys, ... ys .map (y => [... y, x])]
}

Or, the same algorithm in a different style,

const subsets = (
  xs = [], 
  x = xs .slice (-1) [0], 
  ys = xs.length && subsets (xs .slice (0, -1))
) =>
  xs .length == 0
    ? [[]]
    : [... ys, ... ys .map (y => [... y, x])]

Answer 10

A shorter version of @koorchik's answer.

var getAllSubsets = (nums) => {
  const subsets = [[]];
  for (n of nums) {
    subsets.map((el) => {
      subsets.push([...el, n]);
    });
  }
  return subsets;
};

console.log(getAllSubsets([1, 2, 3])); 
// [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Answer 11

For loop:

function powerSet(numbers) {
    const subsets = [[]]
    for (const number of numbers) {
        subsets.forEach(subset => subsets.push([...subset, number]))
    }
    return subsets
}

Recursion:

function powerSet(numbers) {
    const subsets = [[]]
    if (numbers.length === 0) return subsets
    for (let i = 0; i < numbers.length; i++) {
        subsets.push(...powerSet(numbers.slice(i + 1)).map(subset => [numbers[i], ...subset]))
        // Or step by step:
        // const number = numbers[i]
        // const otherNumbers = numbers.slice(i + 1)
        // const otherNumbersSubsets = powerSet(otherNumbers)
        // const otherNumbersSubsetsWithNumber = otherNumbersSubsets.map(subset => [number, ...subset])
        // subsets.push(...otherNumbersSubsetsWithNumber)
    }
    return subsets
}

Answer 12

Using reduceRight:

const subsets = array =>
  array.reduceRight(
    (accumulator, a) => [...accumulator, ...accumulator.map(b => [a, ...b])],
    [[]]
  );
console.log(subsets([1, 2, 3]));  // [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Answer 13

This one is with recursion

var subsets = function(s){
  if(s.length === 0) {
    return [[]]
  }
  var h,t,ss_excl_h;
  var ss_incl_h = [];
  [h,...t] = s;
  ss_excl_h = subsets(t)
  for(ss of ss_excl_h) {
    let hArr = [];
    hArr.push(h);
    let temp = hArr.concat(ss)
    ss_incl_h.push(temp);
  }
  return ss_incl_h.concat(ss_excl_h)
}

console.log(subsets([1,2,3])) // returns distinct subsets

Answer 14

Update ES2020

With ES2020 BigInts have become available.

Bigints don’t have a fixed storage size in bits; their sizes adapt to the integers they represent.

- Dr. Axel Rauschmayer; JavaScript for impatient programmers - Chapter 18.2 BigInts

See source.

Using BitInts we can use a binary counter to calculate the power set and are no longer limited by the maximum integer size.

Using a generator we can additionally loop over a power set with constant memory requirement which is important if you want to generate a huge power set.

Here an example using you original array [1, 2, 3].

/**
 * Generate power set from a given array
 * @param {Array<any>} array array to create power set from
 */
function* powerSet(array){
  // use BigInt to be no longer limited by maximum length of 53-bits
  const size = 2n ** BigInt(array.length); 
  for (let i = 0; i < size; i++) {
    const cur = [];
    for(let j = 0; j < array.length; j++){
      // check if i-th bit is set to 1
      if((i & (1 << j)) > 0){
        // push array value (represented by that 1-bit) to result
        cur.push(array[j]);
      }
    }
    // generate next result
    yield cur;
  } 
}

// generate power set for [1, 2, 3] and print results
console.log([...powerSet([1, 2, 3])]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Here how you could loop over a very large power set with constant memory and no upper bound (theoretically, there will be an upper bound in terms of compute time) for the array length.

/**
 * Generate power set from a given array
 * @param {Array<any>} array array to create power set from
 */
function* powerSet(array){
  // use BigInt to no longer limited by maximum length of 53-bits
  const size = 2n ** BigInt(array.length); 
  for (let i = 0; i < size; i++) {
    const cur = [];
    for(let j = 0; j < array.length; j++){
      // check if i-th bit is set to 1
      if((i & (1 << j)) > 0){
        // push array value (represented by that 1-bit) to result
        cur.push(array[j]);
      }
    }
    // generate next result
    yield cur;
  } 
}

/**
 * Helper function to generate an array containing more than 53 elements
 * @param {number} start 
 * @param {number} end 
 */
function* range(start, end){
  for (let i = start; i < end; i++) {
    yield i;  
  }
}

// create an array containing elments 1 through 60 ([1, 2, 3, ..., 60])
const oneToSixty = [...range(1, 61)];
let i = 0;
const max = 1000; 
// loop over whole powerSet with constant memory requirement
// abort after 1000 subsets, otherwise this will take a very long time to complete
for(const subset of powerSet(oneToSixty)){
  console.log(subset);
  if(i++ === max) break;
}

.as-console-wrapper { max-height: 100% !important; top: 0; }