Categories

Generate All Subsets for a Set using Javascript

The total number of subsets for any given set of size ‘n’ is 2^n (nC0 + nC1 + nC2 + ….. + nCn). In the following program we use all the possible binary values between 0 (inclusive) and 2^n. In every number if it is 1 then the element is in the subset or else it is omitted.

``` const generateSubsets = (inp) => {
if (!Array.isArray(inp)) {
return;
}
var n = inp.length;
var allSubsets = [];

for (var i = 0; i < (Math.pow(2, n)); i++) {
var subset = [];

`     for (var j = 0; j < n; j++) {`
`     if (i & (1 << j)) {`
`      subset.push(inp[j]);`
`    }`
`      }`

`     allSubsets.push(subset);`
}

return allSubsets;
};

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

Demo

Method 2

``` const generateSubsets = (inp) => {
if (!Array.isArray(inp)) {
return;
}
let subsets = [];

for (const val of inp) {
const tempSubsets = […subsets];

for (const currSubset of tempSubsets) {
subsets.push([…currSubset, val]);
}

subsets.push([val]);
}

subsets.push([]);
return subsets;
};

console.log(generateSubsets([1, 2, 3]));
// [[], [1, 2], [2], [1, 3], [1, 2, 3], [2, 3], [3], [0]]```

Demo