题目描述:
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
1 | 输入:nums = [1,2,3] |
示例 2:
1 | 输入:nums = [0] |
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums
中的所有元素 互不相同
链接:
https://leetcode-cn.com/problems/subsets
题目分析
对于 nums
中的每个数,选择或者不选择都是两种不同的情况,也即幂集的个数为 $2^n$。我们可以使用回溯的方法,不选择 nums[i]
进行递归,得到一种结果后回溯,选择 nums[i]
进行递归。每次遍历完 nums[i]
即得到一个结果,将其加入到结果数组中。
1 | class Solution { |
时间复杂度:$O(n\times2^n)$,其中 $n$ 为 nums
数组的大小。因为总共有 $2^n$ 种结果,而对于每种结果我们需要 $O(n)$ 的时间将其加入到答案中。
空间复杂度:$O(n)$,其中 $n$ 为 nums
数组的大小。递归的最大深度为 $n$。