[Day 28] Leetcode 78. Subsets (C++)

前言

今天来看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中这次要不要选取这个数。

结语

倒数第三天了，加油啊~