🔗 🟡 78. Subsets

tags: `回溯(Backtracking)` `子集型回溯` `位運算(Bit Manipulation)` `狀態壓縮`

題意

給定一個整數陣列 $nums$ ，陣列中的元素 互不相同。返回該陣列所有可能的子集，即 Power Set(冪集合) 。

答案中不能包含重複的子集。可以按 任意順序 返回答案。

限制

$1 \leq nums.length \leq 10$
$-10 \leq nums[i] \leq 10$

思路

方法一：回溯(Backtracking)

要構造出所有可能的子集，可以使用回溯法。

令 $path$ 表示當前的子集，對於遍歷到的每個元素，都有兩種可能：在當前子集中或不在當前子集中。因此，可以使用一個遞迴函數 $dfs(i)$ 來遍歷所有元素，其中 $i$ 表示當前遍歷到的元素的索引，當 $i$ 等於陣列的長度時，表示已經遍歷完所有元素，此時將當前的子集加入答案中。

若不選擇當前元素，則直接遞迴到下一個元素，即 $dfs(i+1)$ 。
若選擇當前元素，則將當前元素加入子集中，再遞迴到下一個元素，即 $dfs(i+1)$ ，遞迴結束後，需要將當前元素從子集中移除。

複雜度分析

時間複雜度： $\mathcal{O}(2^n)$ ，每個元素都有 $2$ 種可能，共有 $n$ 個元素，因此共有 $2^n$ 種可能。
空間複雜度： $\mathcal{O}(n)$ ，不計算答案的空間複雜度，遞迴的深度為 $O(n)$ 、 $path$ 的空間複雜度為 $O(n)$ 。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = []
        def dfs(i: int) -> None:
            if i == n: # 到達葉節點
                ans.append(path[:]) # 複製一份，因為是 Reference
                return
            dfs(i + 1) # 不選 nums[i]
            path.append(nums[i])
            dfs(i + 1) # 選 nums[i]
            path.pop()
        dfs(0)
        return ans

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> path;
        function<void(int)> dfs = [&](int i) {
            if (i == n) { // 到達葉節點
                ans.push_back(path); // Array 沒有 Reference 問題
                return;
            }
            dfs(i + 1); // 不選 nums[i]
            path.push_back(nums[i]);
            dfs(i + 1); // 選 nums[i]
            path.pop_back();
        };
        dfs(0);
        return ans;
    }
};

方法二：位運算(Bit Manipulation) + 狀態壓縮

可以注意到陣列的長度最多只有 $10$ ，而每個元素都只有在或不在子集中兩種狀態，所以可以把每個元素的狀態用二進位表示，這樣就可以用一個長度為 $10$ 的二進位數來表示一個子集，並且將枚舉子集轉換成枚舉數字，這就是狀態壓縮。

枚舉 $[0, 2^n)$ 之間的所有數字，對於每個數字的第 $j$ 位，如果該位是 $1$ ，則代表 $nums[j]$ 在當前子集中，將其加入當前子集中即可。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot 2^n)$ ，枚舉所有子集需要 $\mathcal{O}(2^n)$ 的時間，對於每個子集，需要 $\mathcal{O}(n)$ 的時間來檢查每個元素是否在子集中。
空間複雜度： $\mathcal{O}(n)$ ，不計算答案的空間複雜度，需要 $\mathcal{O}(n)$ 的空間來存儲當前子集。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        for i in range(1 << n): # 枚舉所有子集，狀態壓縮
            cur = [] # 當前子集
            for j in range(n):
                if i & (1 << j): # nums[j] 在當前子集中
                    cur.append(nums[j])
            ans.append(cur)
        return ans

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < (1 << n); i++) { // 枚舉所有子集，狀態壓縮
            vector<int> cur; // 當前子集
            for (int j = 0; j < n; j++){ // 檢查 nums[j] 是否在當前子集中
                if (i & (1 << j)) cur.push_back(nums[j]);
            }
            ans.push_back(cur);
        }
        return ans;
    }
};

方法三：生成子集

可以發現，對於任意一個元素 $x$ ，它在子集中有兩種狀態：在或不在。因此，可以從空集合開始，枚舉所有元素，對於每個元素 $x$ ，複製一份當前的所有子集，並在其中添加當前元素 $x$ ，這樣就可以生成所有可能的子集。

上述方法可能有點抽象，可以從二進位數的角度去思考，這裡舉個例子來方便理解：

假設 $nums = [1, 2, 3]$ ，初始化答案為 $[[]]$ ，二進位表示為 $0$ 。
當考慮到元素 $1$ 時，將當前答案複製一份，再把元素 $1$ 添加到其中，得到 $[[], [1]]$ ，二進位表示為 $0, 1$ 。
當考慮到元素 $2$ 時，將當前答案複製一份，再把元素 $2$ 添加到其中，得到 $[[], [1], [2], [1, 2]]$ ，二進位表示為 $00, 01, 10, 11$ 。
當考慮到元素 $3$ 時，將當前答案複製一份，再把元素 $3$ 添加到其中，得到 $[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]$ ，二進位表示為 $000, 001, 010, 011, 100, 101, 110, 111$ 。

可以發現考慮到第 $i$ 個元素時，前 $i-1$ 位會重複出現兩次，只有第 $i$ 位不同。因此當考慮到第 $i$ 個元素時，所有可能的子集是第 $i-1$ 個元素時的所有子集，再從第 $i-1$ 個元素時的所有子集的基礎上，將當前元素 $x$ 添加到所有子集中。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot 2^n)$ ，對於每個元素，需要複製一份當前的所有子集，並在其中添加當前元素，共需要 $2^0 + 2^1 + \cdots + 2^{n-1} = 2^n - 1$ 次子集的複製，而每個子集中有 $O(n)$ 個元素。
空間複雜度： $\mathcal{O}(2^n)$ ，過程中需要存儲所有子集，共有 $2^n$ 個子集。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [[]] # 初始化答案，只包含一個空集合
        for x in nums: # 枚舉所有元素
            ans += [cur + [x] for cur in ans] # 複製一份當前的所有子集，並在其中添加當前元素 x
        return ans

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans = {{}}; // 初始化答案，只包含一個空集合
        for (int x : nums) { // 枚舉所有元素
            int k = ans.size();
            for (int j = 0; j < k; j++) { // 複製一份當前的所有子集，並在其中添加當前元素 x
                vector<int> cur = ans[j];
                cur.push_back(x);
                ans.push_back(cur);
            }
        }
        return ans;
    }
};