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],
[]
]
还是用recursion的方法,只是这次有重复的,要单独处理,例如有三个222连续的情况,那么不是再一个一个的往后recursive的求,不然的话会有重复的,因为12,13和23都是两个2,而结果要求我们只算一次。

所以我们先将所有的number sort一下,然后碰到连续的话就记下连续的个数(222的话就是三个),然后跳过所有连续的求接下来的所有的结果,然后在结果前面append 0 ~ 连续的个数个重复的数即可,(222的话就是分别append [],2,22,222即可)

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        return subsetsWithDupSorted(num, 0, num.length);
    }
    
    public ArrayList<ArrayList<Integer>> subsetsWithDupSorted(int[] num, int start , int  end) // end exclusive for empty array
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (start == end)
        {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            res.add(temp);
            return res;
        }
        
        int dup = start;
        int count = 1;
        for (dup = start + 1; dup < end; dup++) // find dup numbers
        {
            if (num[dup] != num[start])
                break;
            count++;
        }
        
        for(ArrayList<Integer> l : subsetsWithDupSorted(num, dup, end))
        {
            for (int i = 0; i <= count; i++)
            {
                ArrayList<Integer> n = new ArrayList<Integer>();
                for (int j = 0; j < i; j++)
                {
                    n.add(num[start]);
                }
                n.addAll(l);
                res.add(n);
            }
        }
        return res;
    }
}

Second Submission:

Made a mistake of operating directly from recursively returned next array. Need to make new arrays and append elements to make sure correctness.
Use the recursive method, for dups (say we have multiple 2s), if we already tried one position if 2, then we don’t put any other 2 on this position because this will result to same result. But we can still use 2 in the recursive callse

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        return getSubSet(num, 0);
    }
    
    public ArrayList<ArrayList<Integer>> getSubSet(int [] num, int start) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (start == num.length) {// if start reach the end
            ArrayList<Integer> temp = new ArrayList<Integer>();
            result.add(temp);
            return result;
        }
        int c = num[start];
        int count = 1;
        int nextStart = start + 1;
        for(nextStart = start+1; nextStart < num.length; nextStart++) {
            if (num[nextStart] != c)
                break;
            count++;
        }
        ArrayList<ArrayList<Integer>> next = getSubSet(num, nextStart);
        for (ArrayList<Integer> list : next) {
            for (int i = 0; i <= count; i++) {
                // need to copy a new list to put into the result, can not operate on the original list
                ArrayList<Integer> temp = new ArrayList<Integer>(list);
                for (int j = 0; j < i; j++) {
                    temp.add(0, c);
                }
                result.add(temp);
            }
        }
        return result;
    }
}

Same idea,

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        return subsetsWithDupSorted(num, 0, num.length - 1);
    }
    
    public ArrayList<ArrayList<Integer>> subsetsWithDupSorted(int[] num, int start , int  end) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (start > end) {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            res.add(tmp);
            return res;
        }
        int count = 1;
        int i = start + 1;
        while(i <= end && num[i] == num[start]) {
            count++;
            i++;
        }
        int curr = num[start];
        ArrayList<ArrayList<Integer>> next = subsetsWithDupSorted(num, i, end);
        while(count >= 0) {
            for (ArrayList<Integer> list : next) {
                ArrayList<Integer> tmp = new ArrayList<Integer>(list);
                for (int j = 0; j < count; j++) { // add j element
                    tmp.add(0, curr);
                }
                res.add(tmp);
            }
            count--;
        }
        return res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s