WechatIMG625.jpeg
題目描述
leetcode 第90題：子集 II
給你一個整數(shù)數(shù)組 nums ，其中可能包含重復(fù)元素酪耕，請你返回該數(shù)組所有可能的子集（冪集）孽惰。
解集 不能 包含重復(fù)的子集。返回的解集中碑隆，子集可以按 任意順序 排列恭陡。
示例：
輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
解題方法
DFS
參照題解
- 解題思路
獲取整數(shù)數(shù)組
nums的長度n
因為整數(shù)數(shù)組是無序的，需要先對整數(shù)數(shù)組排序
對整數(shù)數(shù)組進行DFS上煤，起始索引index從0開始休玩，初始子集path為空數(shù)組
如果當(dāng)前子集不存在于解集res中，進行插入
在[index,n)區(qū)間繼續(xù)遍歷整數(shù)數(shù)組
如果當(dāng)前索引i大于起始索引劫狠，且nums[i]等于nums[i-1]拴疤，跳過
然后進行下一次DFS，直到解集中包含所有情況的子集
- 復(fù)雜度
時間復(fù)雜度：O(n2^n)
空間復(fù)雜度：O(n2^n)
- 代碼實現(xiàn)
python3
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(index,path):
if path not in res:
res.append(path)
for i in range(index,n):
if i>index and nums[i]==nums[i-1]:
continue
dfs(i+1,path+[nums[i]])
n = len(nums)
nums.sort()
res = []
dfs(0,[])
return res
php
class Solution {
function subsetsWithDup($nums) {
$this->nums = $nums;
$this->n = count($nums);
sort($this->nums);
$this->res = [];
$this->dfs(0,[]);
return $this->res;
}
function dfs($index,$path){
if(!in_array($path,$this->res)){
array_push($this->res,$path);
}
for($i=$index;$i<$this->n;$i++){
if($i>$index && $this->nums[$i]==$this->nums[$i-1]){
continue;
}
$this->dfs($i+1,array_merge($path,[$this->nums[$i]]));
}
}
}
