LeetCode[中等] 78.子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
思路 迭代法
每次遍历nums中的新的数，将其加到之前所有得到的set中，得到的新列表，加到结果列表中
public class Solution {
public IList<IList<int>> Subsets(int[] nums) {
IList<IList<int>> powerSet = new List<IList<int>>();
powerSet.Add(new List<int>());
foreach(int num in nums)
{
int size = powerSet.Count;
for(int i = 0; i < size; i++)
{
IList<int> set = new List<int>(powerSet[i]);
set.Add(num);
powerSet.Add(set);
}
}
return powerSet;
}
}
复杂度分析
- 时间复杂度：O(n×2n)，其中 n 是数组 nums 的长度。子集个数是 2n，对于每个子集需要 O(n) 的时间添加到答案中，因此时间复杂度是 O(n×2n)。
-
空间复杂度：O(n)，其中 n 是数组 nums 的长度。每次新生成子集需要 O(n) 的空间。注意返回值不计入空间复杂度。