> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/subsets-ii.md).

# 90. Subsets II

Given a collection of integers that might contain duplicates, ***nums***, return all possible subsets (the power set).

**Note:** The solution set must not contain duplicate subsets.

**Example:**

```
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
```

## Thoughts

对给定数组返回它的powerset。找所有=>DFS。DFS每步从剩下的元素中选择一个元素。设置当前选择范围的起始位置以避免重复选择之前的元素。Input有重复的数字，要求输出subset不重复。\[1, 2, 2]，在\[1]时选第二个2由于和选第一个2时产生的结果相同，要跳过DFS同一层的其它相同元素。不同层之间相同元素没影响。为了方便跳过相同元素，排序。

## Code

```python
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        def dfs(pos, res, path):
            for i in range(pos, len(nums)):
                if i == pos or nums[i] != nums[i - 1]:
                    path.append(nums[i])
                    dfs(i + 1, res, path)
                    path.pop()
            res.append([i for i in path])
        dfs(0, res, [])
        return res
```

```java
class Solution {
    private void helper(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            helper(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        helper(nums, 0, new ArrayList<>(), res);
        return res;
    }
}
```

## Analysis

最差是没有重复的数, 依然O(N^2).