How to Find All Subsets of a Set in JavaScript? (Powerset of Array)

How to find all subsets of a set in JavaScript? (Powerset of array)

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

Generate all subsets of a set in javascript

The implementation should look like this:

(function(input){
var result, mask, total = Math.pow(2, input.length);
    for(mask = 0; mask < total; mask++){ //O(2^n)
        result = [];
        i = input.length - 1; //O(n)
        do{
            if( (mask & (1 << i)) !== 0){
                result.push(input[i]);
            }
        }while(i--);
        console.log(result);
    }
})(['a','b','c','d','e','f']);

The idea here is to use a number from 0 to n (n is the length of the input array), extract each bit to form decide to pick the element or not.

For example, if you have [a,b,c] as the input, the number will iterate from 0 -> 5, in binary they will be 000, 001, 010, 011, 100, 101, 110, 111 and there for the result would be , c, b, bc, a, ac, ab, abc .

Total running time is O(n2^n).

Finding all subsets of a set, Powerset, recursively by cloning n-1 and adding n to the clones

I gave this a try and came up with

function getSubsets(inp) {
  if (inp.length == 1) {
      // return the single item set plus the empty set
      return [inp, []];
  } else {
      var e = inp.pop();
      var s = getSubsets(inp);
      // duplicate the elements of s into s1 without creating references.  
      // this might not be the best technique
      var s1 = s.concat(JSON.parse(JSON.stringify(s)));
      // add e to the second group of duplicates
      for (var i=s.length; i < s1.length; i++) {
          s1[i].push(e);
      }
      return s1;
  }    
}

var set = ['a', 'b', 'c'];
var list = getSubsets(set);
console.log(list);

// result
//  [["a"], [], ["a", "b"], ["b"], ["a", "c"], ["c"], ["a", "b", "c"], ["b", "c"]]

The lady in the video said that all subsets of {a,b,c} can be formed from taking all the subsets of {a,b} and appending c to each one. Not entirely accurate (a valid subset of {a,b,c} does not have to include c), but a starting place for the algorithm. I changed the rule to all subsets of {a,b,c} can be formed from taking two copies of the subsets of {a,b} and appending c to each element of the second copy.

I think I could get rid of or simplify the if, because essentially the second block of code does the same as the first, so it's not ideal.

To me it makes sense that the algorithm runs in O(2^n) because the results vary in the same way (3 elements in the input array = 2^3 elements in the output array) - you might have to forgive my use of JSON to assume that complexity though. I'd find a better way to deep clone the array, even so, that might add more complexity.

Find all possible subset combos in an array?

After stealing this JavaScript combination generator, I added a parameter to supply the minimum length resulting in,

var combine = function(a, min) {
    var fn = function(n, src, got, all) {
        if (n == 0) {
            if (got.length > 0) {
                all[all.length] = got;
            }
            return;
        }
        for (var j = 0; j < src.length; j++) {
            fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
        }
        return;
    }
    var all = [];
    for (var i = min; i < a.length; i++) {
        fn(i, a, [], all);
    }
    all.push(a);
    return all;
}

To use, supply an array, and the minimum subset length desired,

var subsets = combine([1, 2, 3], 2);

Output is,

[[1, 2], [1, 3], [2, 3], [1, 2, 3]]

Why is my solution for the powerset question incorrect? I have included my recursive and iterative approach

You need to take a copy without object reference.

function powerSet(array) {
    // Write your code here.
    let set = [[]];
    powersetHelper(array, [], set);
    return set;
}

function powersetHelper(array, subset, set) {
    if (array.length === 0) return;
    for (let i = 0; i < array.length; i++) {
        subset.push(array[i]);
        set.push([...subset]); // take copy without object reference
    }
    let newArr = array.slice(1);
    powersetHelper(newArr, [], set)
}

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

.as-console-wrapper { max-height: 100% !important; top: 0; }