子集

题目 子集

思路分析

记原序列中元素的总数为 n

原序列中的每个数字 \(a_i\) 的状态可能有两种

即「在子集中」和「不在子集中」

用 1 表示「在子集中」，000 表示不在子集中

那么每一个子集可以对应一个长度为 n 的 0/1 序列

第 i 位表示 \(a_i\) 是否在子集中

代码实现

class Solution {

public:

    vector<int> t;

    vector<vector<int>> ans;

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

        int n = nums.size();

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

            t.clear();

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

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

                    t.push_back(nums[i]);

                }

            }

            ans.push_back(t);

        }

        return ans;

    }

};

同类题型

视频讲解

⬅️ 二进制枚举子集 🏠 00-刷题理模型 ➡️ 快速幂