Problem: 78. 子集
題目：給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。
解集 不能 包含重復的子集。你可以按 任意順序 返回解集。

整體思路

這段代碼同樣旨在解決 “子集 (Subsets)” 問題。與前面基于回溯/DFS的遞歸解法不同，此版本采用了一種完全不同的、基于 位掩碼（Bitmask） 的迭代方法。這種方法非常巧妙，它將“生成子集”的問題與“二進制數的表示”完美地對應起來。

算法的核心思想是：

1. 子集與二進制數的映射關系

   • 一個包含 n 個元素的集合，其所有子集的數量是 2^n。
   • 巧合的是，從 0 到 2^n - 1，也正好有 2^n 個不同的整數。
   • 我們可以將這 n 個元素與一個 n 位的二進制數的每一位進行一一對應。例如，nums = [a, b, c]，n=3。我們可以用一個 3 位的二進制數來表示一個子集：
     • 第 0 位對應元素 a
     • 第 1 位對應元素 b
     • 第 2 位對應元素 c
   • 規則：如果二進制數的某一位是 1，則表示對應的元素被選中加入子集；如果是 0，則表示不選。
   • 示例：
     • 二進制 000 (十進制 0) -> {} (空集)
     • 二進制 001 (十進制 1) -> {a}
     • 二進制 010 (十進制 2) -> {b}
     • 二進制 101 (十進制 5) -> {a, c}
     • 二進制 111 (十進制 7) -> {a, b, c}
   • 這樣，從 0 到 2^n - 1 的每一個整數，都唯一地對應著一個子集。

2. 算法實現步驟：

   • 外層循環：算法的主體是一個 for 循環，它從 i = 0 遍歷到 (1 << n) - 1。這里的 (1 << n) 就是 2^n。這個循環變量 i 就充當了位掩碼，它的二進制表示決定了當前要生成哪個子集。
   • 內層循環與位運算：
     • 對于每一個位掩碼 i，算法進入一個內層循環，從 j = 0 到 n-1，檢查 i 的每一位。
     • 檢查第 j 位：通過位運算 (i >> j & 1) == 1 來檢查 i 的第 j 位是否為 1。
       • i >> j: 將 i 右移 j 位，使得原來的第 j 位移動到最右邊（第 0 位）。
       • & 1: 將右移后的結果與 1 進行按位與操作。如果原來的第 j 位是 1，結果就是 1；如果是 0，結果就是 0。
     • 構建子集：如果檢查結果為 1，說明 nums[j] 這個元素應該被包含在當前子集中，于是將其加入到臨時的 subset 列表中。
   • 收集結果：內層循環結束后，subset 列表就構建完畢了，將其加入到最終的結果列表 ans 中。

通過這種方式，算法以一種確定性的、非遞歸的方式，系統地生成了所有 2^n 個子集。

完整代碼

class Solution {/*** 計算給定數組的所有子集（冪集）。* (位掩碼迭代法)* @param nums 不含重復元素的整數數組* @return 包含所有子集的列表*/public List<List<Integer>> subsets(int[] nums) {int n = nums.length;// 預先設定ArrayList的容量為 2^n，可以提高性能，避免多次內部擴容。// (1 << n) 是 2^n 的高效寫法。List<List<Integer>> ans = new ArrayList<>(1 << n);// 步驟 1: 外層循環遍歷所有可能的子集，用整數 0 到 2^n - 1 作為位掩碼。for (int i = 0; i < (1 << n); i++) {// 為每個位掩碼創建一個新的子集列表。List<Integer> subset = new ArrayList<>();// 步驟 2: 內層循環檢查位掩碼 i 的每一位，以確定哪些元素應加入子集。for (int j = 0; j < n; j++) {// 關鍵的位運算：檢查 i 的第 j 位是否為 1。// (i >> j) 將 i 的第 j 位移到最右邊。// (& 1)   檢查最右邊一位是否為 1。if ((i >> j & 1) == 1) {// 如果第 j 位為 1，則將 nums[j] 加入到當前子集中。subset.add(nums[j]);}}// 將構建好的子集加入到最終結果列表中。ans.add(subset);}return ans;}
}

時空復雜度

時間復雜度：O(N * 2^N)

1. 外層循環：for (int i = 0; i < (1 << n); i++) 執行 2^N 次。
2. 內層循環：for (int j = 0; j < n; j++) 執行 N 次。
3. 循環內部操作：位運算和 subset.add() 都是 O(1) 的操作。

綜合分析：
算法的總操作次數是外層循環次數乘以內層循環次數，即 2^N * N。
因此，總的時間復雜度為 O(N * 2^N)。這與回溯法的時間復雜度量級是相同的，因為問題的內在計算量就是這么多。

空間復雜度：O(N) (不考慮輸出數組)

1. 主要存儲開銷：我們分析的是額外輔助空間。
   • List<Integer> subset: 在每次外層循環中，都會創建一個臨時的 subset 列表。在任意時刻，只有一個 subset 列表存在于內存中。這個列表的最大長度為 N（當位掩碼為 11...1 時）。因此，這部分空間是 O(N)。
   • 其他變量 n, i, j 都是常數空間。

綜合分析：
如果不考慮存儲最終結果的 ans 列表（其空間為 O(N * 2^N)），算法所需的額外輔助空間主要由臨時的 subset 列表決定。因此，其空間復雜度為 O(N)。

參考靈神