-4

While learning for interviews, I just want to share an example on how to generate all unique subsets of a set in javascript.

ssube
  • 47,010
  • 7
  • 103
  • 140
Dewey
  • 1,193
  • 14
  • 18
  • Possible duplicate [This may help][1] [1]: http://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array – Lonely Aug 13 '13 at 08:28
  • @Lonely, it is not duplicate and the answered algorithm is not even efficient. – Dewey Aug 13 '13 at 17:24

1 Answers1

9

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).

Dewey
  • 1,193
  • 14
  • 18
  • We actually have 2^n - 1 combinations, since the first one in this case is always 0. Wouldn't it be more optimal if "mask" would start at 1 instead of 0? – just_a_girl Nov 11 '16 at 18:15
  • Your answer also fits this question: http://stackoverflow.com/questions/42773836/how-to-find-all-subsets-of-a-set-in-javascript - you might want to post it there, too. – le_m Mar 13 '17 at 21:46