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.

 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

Categories
interview

Convert Integer to Binary using Javascript

var test = 3;
var pow;
var str='';
for(var i=0; (test/Math.pow(2,i)) > 1; i++) {
 pow = i;
}

for (var j=pow; j>=0; j--) {
 if ( (test & (1<<j)) > 0) 
 str = str + '1';
 else
 str = str + '0';
}
console.log(str);
// logs the value 11 to console.

 

Demo