# 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/exhaustive-search/subsets-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.