78. 子集

1. 選或不選（還原現場）

每一個位置的數字選或不選，然後繼續遞迴呼叫即可。
如果現在要選的數字位置已經到了尾端，就代表遞迴終止。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        vector<int> cur;
        auto dfs = [&](this auto&&dfs, int i) -> void {
            if(i == n) {
                res.push_back(cur);
            }
            else {
                dfs(i + 1); // 不選
                cur.push_back(nums[i]);
                dfs(i + 1); // 選
                cur.pop_back(); // 還原現場
            }
        };
        dfs(0);
        return res;
    }
};

2. 選或不選（size 輔助變數）

假如現在不想要還原現場，能用一個輔助變數size代表當前有效的位數。
舉例來說，現在nums = [1,2,2,3]。
最初都不選，遞迴到底端是dfs(4,0)，這時size到最後都是0，而i已經到n。
往上回傳給dfs(3,0)，它會先讓curPath[0] = nums[3]接著呼叫dfs(4, 1)，代表現在選了第一個數字3
dfs(4,1)會根據size，取curPath的適當長度，將[3]加入到答案當中。後面就算有前面遞迴留下來的資料，也不會影響到結果。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        vector<int> curPath(n); // 路徑最長是全選，因此初始化大小 n
        // i: 當前索引
        // size: 當前大小
        auto dfs = [&](this auto&&dfs, int i, int size) -> void {
            if(i == n) { // 沒有數字要選，將路徑加入倒答案當中
                res.push_back(vector<int>(curPath.begin(), curPath.begin() + size));
            }
            else {
                // 選或不選
                dfs(i + 1, size);
                curPath[size] = nums[i];
                dfs(i + 1, size + 1);
            }
        };
        dfs(0, 0);
        return res;
    }
};

3. 二進制

除了遞迴解之外，也能用二進制去代表當前的組合方式。
假如當前有一個二進制是 $110011$，那就代表要選擇 $0,1,4,5$ 這四個數字做組合。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        for(int i = 0; i < 1 << n; ++i) { // i 以二進制表示選或不選
            vector<int> cur;
            for(int j = 0; j < n; ++j) {
                if(i & (1 << j)) { // 取得對應位置, 看有沒有要選
                    cur.push_back(nums[j]);
                }
            }
            res.push_back(cur);
        }   
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\times{2^n})$
• 空間複雜度：$O(n)$