javascript - javascript でセットのすべてのサブセットを生成する

Question

インタビューの学習中に、JavaScript でセットの一意のサブセットをすべて生成する方法の例を共有したいと思います。

Answer 1

実装は次のようになります。

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

ここでの考え方は、0 から n (n は入力配列の長さ) までの数値を使用し、各ビットを抽出して要素を選択するかどうかを決定することです。

たとえば、入力として [a,b,c] がある場合、数値は 0 -> 5 から繰り返され、2 進数では 000、001、010、011、100、101、110、111 となります。結果は , c, b, bc, a, ac, ab, abc になります。

合計実行時間は O(n2^n) です。