LeetCode 筆記：Subsets（子集，無重複元素）

一、題目描述

給定一組 不含重複元素 的整數數組 nums，返回其所有可能的子集（冪集）。

注意： 子集內元素需非遞減排序，解集不含重複子集。

範例： nums = [1,2,3] → 輸出包含 8 個子集（包括空集）。

二、題目分析

對於 n 個元素，共有 2^n 個子集。常見兩種方法：

1. 位運算法：用 n 位二進制數表示每個元素是否選取。遍歷 0 ~ 2^n-1，按位檢查構建子集。
2. DFS 回溯法：遞歸構建，每層決定「選」或「不選」當前元素，或用 start 索引避免重複組合。

三、示例代碼（C++）

方法一：位運算

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int total = 1 << n; // 2^n
        vector<vector<int>> result;
        for (int mask = 0; mask < total; ++mask) {
            vector<int> subset;
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) subset.push_back(nums[i]);
            }
            result.push_back(subset);
        }
        return result;
    }
};

方法二：DFS 回溯

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        vector<int> path;
        dfs(nums, 0, path, result);
        return result;
    }
private:
    void dfs(const vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
        result.push_back(path);
        for (int i = start; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            dfs(nums, i + 1, path, result);
            path.pop_back();
        }
    }
};

四、小結

位運算法思路直觀，適合小規模 n；DFS 回溯法更通用，易擴展至含重複元素的 Subsets II。時間複雜度均為 O(n * 2^n)。