bitmask を使って部分集合を列挙する問題を解く

leetCode の「78. Subsets」の「Solution」に、面白い＆今後も使えそうな解法があったので、それを元に実装したコードをブログに書いておく。
https://leetcode.com/problems/subsets/

この解法は、与えられた集合体の部分集合を列挙する問題を解く問題などに有効。概要を簡単に説明すると、例えば、与えられた集合体の要素数が 3 だったら、000, 001, 010, 011, ... , 110 ,111 といった bitmask 列を生成する。そして、各 bitmask について、「0」は対応する要素を選択しない、「1」は対応する要素を選択する、といった感じで部分集合を作成していく。つまり、{1 ,2, 3} が与えられた集合体で、bitmask が 011 だったら、部分集合は {2, 3} となる。
これを各 bitmask 毎に繰り返すことで、全部分集合を求めることができる。

    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<String> bitMasks = new ArrayList<>();
        for (int i = (int)Math.pow(2, len); i < (int)Math.pow(2, len + 1); i++) {
            // ★先頭の bit (1) は不要なので、取り除く。
            // これにより、例えば、len = 3 の時、以下の bitmask 達が生成される。
            // 000, 001, 010, 011, ..., 110 ,111
            String bitMask = Integer.toBinaryString(i).substring(1);
            bitMasks.add(bitMask);
        }

        List<List<Integer>> subsets = new ArrayList<>();
        for (String bitmask : bitMasks) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < bitmask.length(); i++) {
                // bit が立っている時 ( 1 の時)、対応する数値を subset に入れる。
                if (bitmask.charAt(i) == '1') {
                    subset.add(nums[i]);
                }
            }
            subsets.add(subset);
        }
        return subsets;
    }

上記コードの ★ を付けたところがポイント(小技)。

こういった問題は、backtracking で解くしかないと思っていたが、こっちの方法の方が簡単そうなので、今後は bitmask を使って解いていきたい。