> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/subsets-ii.md).

# 90. Subsets II

### Description

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.

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/subsets-ii/)
* [ProgramCreek](https://www.programcreek.com/2013/01/leetcode-subsets-ii-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[1, 2, 2]

**Output:** \[ \[], \[1], \[1, 2], \[2], \[1, 2, 2], \[2, 2] ]
{% endtab %}

{% tab title="Example 2" %}
**Input:** \[4, 1, 2, 2]

**Output:** \[ \[], \[1], \[1, 2], \[2], \[1, 2, 2], \[2, 2], \[1, 2, 2, 4], \[1, 2, 4], \[1, 4], \[2, 2, 4], \[2, 4], \[4] ]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

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

    private void backtrack(List<List<Integer>> subsets,
                          LinkedList<Integer> subset,
                          int[] nums,
                          int index) {
        subsets.add(new ArrayList(subset));
        for(int i = index; i < nums.length; i++) {
            if (i > index && nums[i-1] == nums[i]) continue;
            subset.add(nums[i]);
            backtrack(subsets, subset, nums, i+1);
            subset.removeLast();
        }
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList());
        
        Arrays.sort(nums);
        
        for(int i = 0, start = 0, end = 0; i < nums.length; i++) {
            start = 0;
            
            if(i > 0 && nums[i-1] == nums[i]) {
                start = end+1;
            }
            
            end = subsets.size()-1;

            for(int j = start; j <= end; j++) {
                List<Integer> subset = new ArrayList(subsets.get(j));
                subset.add(nums[i]);
                subsets.add(subset);
            }
        }
        return subsets;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*