题目描述
leetcode 第90题:子集 II
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
解题方法
DFS
参照题解
- 解题思路
获取整数数组
nums
的长度n
因为整数数组是无序的,需要先对整数数组排序
对整数数组进行DFS,起始索引index
从0开始,初始子集path
为空数组
如果当前子集不存在于解集res
中,进行插入
在[index,n)
区间继续遍历整数数组
如果当前索引i
大于起始索引,且nums[i]
等于nums[i-1]
,跳过
然后进行下一次DFS,直到解集中包含所有情况的子集
- 复杂度
时间复杂度:O(n2^n)
空间复杂度:O(n2^n)
- 代码实现
python3
1 | class Solution: |
php
1 | class Solution { |