The type of elements in the array
The array to generate subsets from
An array containing all possible subsets
const numbers = [1, 2, 3];
const allSubsets = ArrayUtil.subsets(numbers);
console.log(allSubsets);
// [
// [1, 2, 3], // {1, 2, 3}
// [1, 2], // {1, 2}
// [1, 3], // {1, 3}
// [1], // {1}
// [2, 3], // {2, 3}
// [2], // {2}
// [3], // {3}
// [] // empty set
// ]
const colors = ["red", "blue"];
const colorSubsets = ArrayUtil.subsets(colors);
console.log(colorSubsets);
// [
// ['red', 'blue'],
// ['red'],
// ['blue'],
// []
// ]
// Warning: Result size grows exponentially with array size
// Example: 10 elements → 1,024 subsets, 20 elements → 1,048,576 subsets
contracts/common.md#principled-implementation A depth-first search decides for each position whether the element is in the subset, including it first, and each leaf materializes the chosen elements with filter, so the 2^n subsets appear in a fixed order, the whole array first and the empty array last; the recursion depth is the array length and the output size is exponential, which bounds the useful input size.
contracts/common.md#clear-and-simple-design One recursive function over a mask, with no options.
Generates all possible subsets of a given array.
Implements the mathematical concept of power set, generating 2^n subsets from an array of n elements. Uses depth-first search (DFS) algorithm to calculate all possible combinations of including or excluding each element. Each element is included before it is excluded, so the first subset is the whole array and the last one is empty.
Processing cost: The DFS visits the include/exclude tree and filters N input positions at each of 2^N leaves. This is O(N 2^N) time and materialized output space, the scale required by returning every subset, with O(N) recursion/mask state.