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) 的空间。注意返回值不计入空间复杂度。