是的，在下我現在嘴巴還在麻，預估今晚不用睡了
因為是水平智齒的關係，真的不能不拔，而且這是上個月底就預定的，沒辦法。
顧及團隊精神，而且團隊內的組員其實每個人都是忙中硬ㄍㄧㄥ住，大家都這麼努力，我應該也要努力硬著頭皮寫下去

但所謂的智齒…根本製杖

題目：
請寫一個方法，輸入裡面東西不重複的int集合（set），請找出他所有的子集（subset）
（這題和CTCT 8.4 一模一樣）

舉例：
請看LeetCode上的舉例（太長啦）

點我前往LeetCode題目

那在開始前不乏提醒一下此系列的固定提醒：

這是一系列逐漸帶入解題的文章，難度會隨著進度增加，若還沒有讀過前面的文章，建議先從最前面開始來逐漸練習解題喔！

先和大家說一下，這題有兩個解法，一個是今天要說的，利用位元來解。另一個則是使用遞迴，那遞迴解法我們留到遞迴系列再提。

大家不知道還記不記得，之前說過二進位就好比電燈開或關的樣子

我們上一張圖，請大家看一下：

右方黑色請想像成開，灰色表示關，其實每個subset就像是一種電燈開關的組合！

以上面圖為例，空的subset就代表，原本set中所有數字的狀態為關。[3, 5]就代表1的狀態是關，3、5的狀態是開。

如果我們把set內所有開和關的組合loop過一次，然後轉換成對應的subset……不就是正確答案了嗎！？

我們先上程式碼再慢慢解釋：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for(int i=0 ; i<(1<<nums.length) ; i++) {
            List<Integer> newlist = new ArrayList<Integer>();
            int index = 0;
            for(int j = i ; j > 0 ; j >>= 1) {
                if((j & 1) == 1) newlist.add(nums[index]);
                index++;
            }
            list.add(newlist);
        }
        return list;
    }
}

for(int i=0 ; i<(1<<nums.length) ; i++)

為什麼i要小於(1<<nums.length)呢？因為subset的總數為 2^n 個 (n=set長度)，因為每個set中的數字都開關組合，所以就是2x2x2x...x2x2，很好想像吧？

而i會從二進位的000000到指定長度的111111，所以i就等於一種電燈開關的狀態，我們能利用這個特性來製造subset！

for(int j = i ; j > 0 ; j >>= 1) {
    if((j & 1) == 1) newlist.add(nums[index]);
        index++;
    }

上面的j又是什麼意思呢？記得我們最外層的i代表著一種set內數字的開關組合嗎？j迴圈就是依照這個組合，把要的數字塞進新的subset內。

(j&1)就代表取出j的最後一個位元，如果是1，就代表那個位置是開。之後j整個右移，就可以比對下一個位元。

而index就是負責幫我們記現在比對到set中哪個東西用的。

其實沒有想像中的難，對吧？

因為在下今天狀況奇差，寫的不是很好，還望大家見諒