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

# 0090. Subsets II

<https://leetcode.com/problems/subsets-ii>

## Description

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]]
```

**Constraints:**

* `1 <= nums.length <= 10`
* `-10 <= nums[i] <= 10`

## ac

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

    private void backtrack(int[] nums, int start, List<List<Integer>> res, List<Integer> note) {
        res.add(new ArrayList<Integer>(note));

        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i-1]) continue;  // skip duplicate
            note.add(nums[i]);
            backtrack(nums, i+1, res, note);
            note.remove(note.size()-1);
        }
    }
}
```

Sub-optimal with boolean array.

```java
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];

        Arrays.sort(nums);
        process(nums, 0, tmp, visited, res);

        return res;
    }

    private void process(int[] nums, int start, List<Integer> tmp, boolean[] visited, List<List<Integer>> res) {
        res.add(new ArrayList<>(tmp));

        if (start >= nums.length) return;

        for (int i = start; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue; // duplicate
            tmp.add(nums[i]);
            visited[i] = true;
            process(nums, i + 1, tmp, visited, res);
            visited[i] = false;
            tmp.remove(tmp.size() - 1);
        }
    }
}
```