前言

今天來看top 100 liked的另外一medium題─78. Subsets。整個題目很單純，也沒有什麼限制，但有很多不一樣的做法可以取得答案。

想法

第一個想到的是會有幾種答案呢？答案是2^n種(n=nums.size())，因為針對nums裡面的每一個元素，都可以選擇取或不取該數，所以有2種選擇，而每一個元素都有兩種選擇，因此為2^n。

recursive

而我的想法就很單純，既然每一位都可以選擇取或不取，那就用recursive的方式來對每一位去做取或不取的選擇，如下：

class Solution {
public:
    void helper(vector<vector<int>>& ans, vector<int>& nums, vector<int>& temp, int i) {
        // the last one
        if(i==nums.size()-1){
            // not choose
            ans.push_back(temp);
            // choose
            temp.push_back(nums[i]);
            ans.push_back(temp);
        }
        // not the last one
        else{
            // not choose
            helper(ans, nums, temp, i+1);
            // choose
            temp.push_back(nums[i]);
            helper(ans, nums, temp, i+1);
        }
        temp.pop_back();
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> temp;
        int i=0;
        // for each elements, either chosen or not chosen
        helper(ans, nums, temp, i);
        return ans;
    }
};

可以注意一下我現在在function的傳遞都選擇使用傳參考的方式，因為這樣可以避免每次都要重新copy一整個vector移動來移動去，而使用這種方式要注意的就是push_back完後要pop_back，要不我在下一個recursive的時候取到的就會是已經被push_back後的值了。而我使用i代表目前檢查到那一個位數。
從討論區中可以看到各式解法，這裡有一篇整合了C++的各式解法，大略整理除了上述recursive的解法如下：

Iterative

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]); 
                subs.back().push_back(num);
            }
        }
        return subs;
    }
}; 

概念：
開雙層迴圈，第一層是nums的大小，第二層是目前answer set的大小；現在vector每新增一個數，我們就會變成多兩倍的組合─不選這個數就會=前面目前的全部組合，而選這個數就是把前面全部的組合都複製一次，然後加入目前這個數。每次會針對原本的再複製一次，後面加上現在的num。

Bit Manipulation

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size(), p = 1 << n;
        vector<vector<int>> subs(p);
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < n; j++) {
                if ((i >> j) & 1) {
                    subs[i].push_back(nums[j]);
                }
            }
        }
        return subs;
    }
};

概念:
第一層迴圈是2^n，代表全部的組合；第二層迴圈是nums的大小，針對每一個數去對看2^n的bitset中這次要不要選取這個數。

結語

倒數第三天了，加油啊~