东莞疫情什么时候开始的_90平方设计_在线子域名二级域名查询工具_谷歌google官网下载

原题地址：78. 子集 - 力扣（LeetCode）

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的

子集

（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

解题思路

1. 题目要求：给定一个整数数组 nums，返回该数组所有可能的子集（幂集）。
2. 解决方法：使用位运算，将数组中每个元素看作一个二进制位，通过遍历 0 到 (1 << n) - 1 的所有二进制数，生成对应子集。
   • 每个二进制数表示是否包含某个元素（0表示不包含，1表示包含）。
   • 遍历所有可能的二进制数，逐位检查，生成子集并添加到结果列表中。

源码实现

class Solution {// 临时存储当前子集的列表List<Integer> t = new ArrayList<Integer>();// 存储所有子集结果List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> subsets(int[] nums) {int n = nums.length; // 数组长度// 遍历所有可能的子集，用二进制表示子集选择for (int mask = 0; mask < (1 << n); ++mask) { t.clear(); // 清空临时列表，准备生成新子集for (int i = 0; i < n; ++i) { // 判断当前元素是否在子集中if ((mask & (1 << i)) != 0) { t.add(nums[i]); // 添加当前元素到子集}}// 将当前生成的子集加入结果ans.add(new ArrayList<Integer>(t));}return ans; // 返回所有子集}
}

复杂度分析

1. 时间复杂度：

   • 外层循环：mask 的范围是 [0, 2^n - 1]，共 2^n 次。
   • 内层循环：对于每个 mask，需要遍历数组长度 n 判断当前元素是否属于子集。
   • 总时间复杂度：O(n * 2^n)。

2. 空间复杂度：

   • 临时子集 t：空间需求为 O(n)。
   • 结果集 ans：需要存储所有子集，子集数量为 2^n，平均每个子集大小为 O(n)，总空间需求为 O(n * 2^n)。
   • 因此，空间复杂度为：O(n * 2^n)。