Question

link

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 S = [1,2,2], a solution is: 

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]


      </div>

Stats

Frequency 2
Difficulty 4
Adjusted Difficulty 3
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a question based on “Subsets” question.

Solution is similar, only need to add features to avoid duplication.

Solution

Based on the solution of previous question, I only add 1 variable called nonDupSize, which is the size that I need to merge new element with. For example, input = {1, 2, 3, 3}

Initialize the subset: {}

Added element “1”: {}, {“1”} (1 more elements)

Added element “2”: {}, {“1”}, {“2”}, {“1”, “2”} (2 more elements)

Added element “3”: {}, {“1”}, {“2”}, {“1”, “2”}, {“3”}, {“1”,”3”}, {“2”,”3”}, {“1”, “2”,”3”} (4 more elements)

Added element “3”: {}, {“1”}, {“2”}, {“1”, “2”}, {“3”}, {“1”,”3”}, {“2”,”3”}, {“1”,”2”,”3”}, {“3”,”3”}, {“1”,”3”,”3”}, {“2”,”3”,”3”}, {“1”,”2”,”3”,”3”} (4 more elements)

So instead of getting every list and merge with new element, I only get the lists of pre-calculated size (from bottom), and merge. Someone is having similar solution using a start-pointer.

Code

my code

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    ans.add(new ArrayList<Integer>());
    Arrays.sort(num);
    // In this solution I introduce a new variable: nonDupSize
    int curSize = 1, nonDupSize = 1;
    for (int i = 0; i < num.length; i ++) {
        curSize = ans.size();
        if (i > 0 && num[i] != num[i - 1]) nonDupSize = curSize;
        for (int j = curSize - nonDupSize; j < curSize; j ++) {
            ArrayList<Integer> cur = new ArrayList<Integer>(ans.get(j));
            cur.add(num[i]);
            ans.add(cur);
        }
    }
    return ans;
}

Updated on June 12th - solution using the ‘Permutation Model’.

public List<List<Integer>> subsetsWithDup(int[] num) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(num == null || num.length == 0) {
        return result;
    }
    Arrays.sort(num);
    helper(result, new LinkedList<Integer>(), num, 0);
    return result;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int position) {
    ans.add(new LinkedList<Integer>(path));
    for (int i = position; i < num.length; i ++) {
        if (i > position && num[i - 1] == num[i]) {
            // if duplicate, only append num[position]
            continue;
        }
        path.add(num[i]);
        helper(ans, path, num, i + 1);
        path.remove(path.size() - 1);
    }
}