Categories
interview

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.

var set = [1,2,3];
var n = set.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)) > 0 )
     subset.push(set[j]);
 }
 allSubsets.push(subset);
}

console.log(allSubsets);

// Should output [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

Demo

Method 2

var set = [1, 2, 3];
var allSubsets = [0];

var addToElems = function(curr) {
 if(allSubsets.length === 1) return;
 var tmp = [];
 var tmpry = [];
 for(var k=1; k<allSubsets.length; k++) {
   if(Array.isArray(allSubsets[k])) {
     tmp = allSubsets[k].slice();
     tmp.push(curr);
    } else {
     tmp.push(allSubsets[k], curr);
    }
   tmpry.push(tmp);
   tmp = [];
 }

 for(var j=0; j<tmpry.length; j++) {
   allSubsets.push(tmpry[j]);
 }
return;
};


for (var i=0; i < set.length; i++) {
 addToElems(set[i]);
 allSubsets.push(set[i]);
}

console.log(allSubsets);

// Should output 0, 1, [1,2], 2, [1,3], [1,2,3], [1,2], 3

Demo