## Given problem

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

## Using Backtracking algorithm

1. The easiest way is that before we push an array into a result array, we will check whether it can be duplicated the other array in result array or not.

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

return res;
}

public void subsetsWithDup(int[] nums, List<List<Integer>> res, List<Integer> values, int indx) {
if (!res.contains(values)) {
}

for (int i = indx; i < nums.length; ++i) {
subsetsWithDup(nums, res, values, i + 1);
values.remove(values.size() - 1);
}
}
``````
2. Compare elements in the loop

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

return res;
}

public void subsetsWithDup(int[] nums, List<List<Integer>> res, List<Integer> values, int indx) {

for (int i = indx; i < nums.length; ++i) {
if (i != indx && nums[i] == nums[i - 1]) {  // compare the current element and previous element
continue;
}

subsetsWithDup(nums, res, values, i + 1);
values.remove(values.size() - 1);
}
}
``````

The complexity of this problem:

• Time complexity: O(n * 2^n)
• Space complexity: O(n * 2^n)

## Wrapping up

• Understanding basic about the structure of backtracking problem.

Refer:

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