Subsets II

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

solution1：DFS, recursion

这一题是上面Subset I的延伸，在这一题种，输入集合有重复的元素了，但是要求输出结果不能有重复的Set

例如，假设集合为［2，3，3］，如果按照Subset I的程序不做改动，会出现什么情况呢

[]

[2]

[2,3]

[2,3,3]

[2,3] //把最后一个3删去，再把倒数第二个3删去，此时集合剩下［2］，此层的循环还没完，还可以取最后一个，3，所以生成了重复的集合［2，3］

[3]

[3,3]

[3] //同理，把最后一个3删去，再把倒数第二个3删去，第一层循环还可以取最后一个数3，所以生成了重复的集合[3]

那么，我们需要做的是，在删去元素后，再取元素的时候，不要取和刚刚取过的元素相等的元素。

public class Solution {
    public ArrayList> subsetsWithDup(int[] num) {
        ArrayList> res = new ArrayList>();
        ArrayList list = new ArrayList();
        Arrays.sort(num);
        res.add(list);
        if(num == null || num.length == 0)
            return res;
        select(num, 0, res, list);
        return res;
    }
    
    public void select(int[] num, int pos, ArrayList> res, ArrayList list) {
        for(int i = pos; i < num.length; i++) {
            list.add(num[i]);
            res.add(new ArrayList (list));
            select(num, i+1, res, list);
            list.remove(list.size() - 1);
            while(i < num.length - 1 && num[i+1] == num[i])  //如果和刚取过的元素相等，i++
                i++;
        }
    }
}

solution2：iterator

public class Solution {
    public ArrayList> subsetsWithDup(int[] num) {
        ArrayList> res = new ArrayList>();
        ArrayList list = new ArrayList();
        res.add(list);
        if(num == null || num.length == 0) {
            return res;
        }
        
        Arrays.sort(num);
        int start = 0;
        for(int i = 0; i < num.length; i++) {
            int size = res.size();
            for(int j = start; j < size; j++) {
                list = new ArrayList(res.get(j));
                list.add(num[i]);
                res.add(list);
            }
            if(i < num.length - 1 && num[i] == num[i + 1]) {  //deal with the duplicate elements
                start = size;
            }else {
                start = 0;
            }
        }
        
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/24613193