LeetCode 78. Subsets [Medium] [C++] 解題筆記

這題給定一個 array，其中所有數字不重複，要我們求 array 中所有數字可以組成的不重複子集。

EX:

        nums = [1,2,3]

Ans: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

想法:

        這題其實可以想成是組合的題目，基本上可以用這題 77. Combinations 的作法來做，只要對所有長度的子集分別求他們的可能的組合即可。

另外這題還有一個比較巧妙的解法，因為每個子集可以想像成集合裡的元素取或不取的組合，

所以共有 2^n 個子集，即 {0,1, ... , n - 1} 的子集合 S 可以用整數值的二進位編碼成 f(S) = Σ 2^i，i 屬於 S，因此表示我們可以利用 2^i 為 0 或 1 來表示 index i 的元素是否在某個子集合中，例如 {1, 2, 3} 的子集可以用三個位元的二進位數字來表示，如 {1, 2, 3} 表示 111，{2, 3} 表示 011，因此要判斷 index i 的元素是否在某個子集合 S 中時，我們只需要判斷 S & (1 << i ) 如果等於 1 表示在 S 中的從右往左的第 i 位是 1(從 0 開始數) ，則 S 包含index i 的元素。(ex: nums = {1,2,3}, 子集 S = {2, 3}, 二進位表示: 011 , i = 1 (第二個數字 ) => 011 & (1 << 1) = 011 & 010 = 010 = 1(true))。

因此這題我們可以知道總共的子集個數會有 2^n 個，我們再遍歷每個子集然後利用上述方式找出每個子集所包含的元素是誰。

完整程式碼:

解法一 (dfs with prune):

class Solution {

public:

    vector<vector<int>> res;

    void comb(vector<int>& nums, vector<int>& cur, int k) {

        if (k == cur.size()) {

            vector<int> tmp(cur.size());

            for (int i = 0; i < cur.size(); i++) {

                tmp[i] = nums[cur[i]];

            }

            res.emplace_back(tmp);

            return;

        }

        

        int s = cur.empty()? 0 : cur.back() + 1;

        for (int i = s; i < nums.size() - (k - cur.size()) + 1; i++) {

            cur.emplace_back(i);

            comb(nums, cur, k);

            cur.pop_back();

        }

        return;

    }       

    vector<vector<int>> subsets(vector<int>& nums) {

        for (int i = 0; i <= nums.size(); i++) {

            vector<int> cur;

            comb(nums, cur, i);

        }

        return res;

    }

};

解法二(bitwise operation):

class Solution {

public:

    vector<vector<int>> subsets(vector<int>& nums) {

        const int n = nums.size();

        vector<vector<int>> res;

        // enumerate all subsets, total 2^n subsets

        for (int i = 0; i < (1 << n); i++) {

            vector<int> cur;

            for (int j = 0; j < n; j++) {

                // check if the j-th element is in this subset

                if (i & (1 << j)) {

                    cur.emplace_back(nums[j]);

                }

            }

            res.emplace_back(cur);

        }

        

        return res;

    }

};