---
# System prepended metadata

title: 90. Subsets II
tags: [Leetcode, medium, python, backtracking]

---

###### tags: `Leetcode` `medium` `backtracking` `python`

# 90. Subsets II

## [題目連結:] https://leetcode.com/problems/subsets-ii/

## 題目:
Given an integer array ```nums``` that may contain duplicates, return all possible subsets (the power set).

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**
```
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
```
**Example 2:**
```
Input: nums = [0]
Output: [[],[0]]
```

## 解題想法:
兄弟題目: [78. Subsets](/6rlh0Wa6Q-O2pCTLxXMdFw)

* 題目為，給一組nums可能含重複數字，求其不重複的power set組合
* 遞迴求解: dfs傳遞參數
    * nums:數組
    * cur_pos:當前數組使用位置
    * path:當前list
    * **每次需判斷，當前的值，是否與前一數相同**
        * 若重複，則跳過

## Python:
``` python=
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        #需先排序
        nums.sort()
        self.res=[]
        self.dfs(nums,0,[])
        return self.res
    def dfs(self,nums,pos,path):
        self.res.append(path)
        for i in range(pos,len(nums)):
            #若遇到重複數 跳過
            if i>pos and nums[i]==nums[i-1]:
                continue
            self.dfs(nums,i+1,path+[nums[i]])

result = Solution()
nums = [1,2,2]
ans = result.subsetsWithDup(nums)
print(ans)
```