> For the complete documentation index, see [llms.txt](https://emmaguo100.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://emmaguo100.gitbook.io/leetcode/02-16-2022-90.md).

# 02/16/2022 90

Subsets II

Method:

Difference from 78:

1. there are duplicate elements in the array

So in order to avoid duplicate subset, we should sort the array first. In the backtracking function, when i > startIndex and nums\[i] == nums\[i-1], we just ignore it and continue.

Time O(n \* 2^n)

Space O(n)

class Solution { List\<List> result = new ArrayList<>(); LinkedList path = new LinkedList<>();

```
public List<List<Integer>> subsetsWithDup(int[] nums) {
    if(nums == null || nums.length == 0) return result;
    Arrays.sort(nums);
    backtracking(nums, 0);
    return result;     
}

private void backtracking(int[]nums, int startIndex){
    result.add(new ArrayList(path));
    if(startIndex >= nums.length) return;
    for(int i = startIndex; i < nums.length; i++){
        if(i > startIndex && nums[i] == nums[i-1]) continue;
        path.add(nums[i]);
        backtracking(nums, i + 1);
        path.removeLast();
    }
}
```

}