Given a collection of integers that might contain duplicates,

*S*, return all possible subsets.**Note:**

- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.

For example,

If

If

**=***S*`[1,2,2]`

, a solution is:[ [2], [1], [1,2,2], [2,2], [1,2], [] ]

**Understand the problem:**

This is an extension of the last problem. The major difference is the array contains duplicates. It asks for returning all distant subsets.

For the input S = [1, 2, 2], if we use exactly the same approach as the last problem, what shall we get?

**Solution:**

Similar to the permutation II, we check the range from start to i contains duplicated numbers, if yes, simply jump to next iteration.

**Code (Java):**

public class Solution { public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (num == null || num.length == 0) return result; Arrays.sort(num); result.add(new ArrayList<Integer>()); ArrayList<Integer> temp = new ArrayList<Integer>(); subsetsHelper(num, 0, temp, result); return result; } private void subsetsHelper(int[] num, int start, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> result) { if (start >= num.length) return; for (int i = start; i < num.length; i++) { if (!isDup(num, start, i)) { temp.add(num[i]); result.add(new ArrayList<Integer>(temp)); subsetsHelper(num, i + 1, temp, result); temp.remove(temp.size() - 1); } } } private boolean isDup(int[] num, int start, int end) { for (int i = start; i <= end - 1; i++) { if (num[i] == num[end]) return true; } return false; } }

**Discussion:**

This problem has time complexity of O(2^n), since finding all subsets of a set is a NP problem.

**Summary:**

The take away message is all permutation and combination questions share very similar ways of solution. Make sure to understand the details.

## No comments:

## Post a Comment