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

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

Solution 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]));

Solution 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ⁿ).

Solution 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; }

Solution 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]