How to find all subsets of a set in JavaScript?

问题:

I need to get all possible subsets of an array.

Say I have this:

[1, 2, 3]

How do I get this?

[], [1], [2], [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

回答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]));

回答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ⁿ).

回答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; }

回答4:

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.