问题描述:

While learning for interviews, I just want to share an example on how to generate all unique 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).

相关阅读:
Top