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

这个题在上一个的基础上增加了重复数字。那么怎么处理这些重复数字呢？我们先定义一个插入点，即每次递归返回到上一层时需要从哪个集合开始插入num[index].分两种情况：

1、当此时的num[index]!=num[index+1]时，我们从集合的第一个元素开始插入。

2、当num[index]==num[index+1]时，我们就要注意插入位置了。此时又分两种情况。

1.如果说insertNum为0，也就是说一开始就是相同的数字如数组[2,2] 那么在最后一个元素插入即可。2的subset是[],2，那么[2,2]的subset是[],2,22，也就是从2开始插入的；
2.如果说不为0，那么就是从tmp.size()-insertNum开始插入。如[1,2,2],2的subset是[],2，那么[1,2]的subset是[],2,1,12.此时记录insertNum为[1,2]的长度也就是2.那么[1,1,2]的subset在[1,2]的基础上从tmp.size()-insertNum开始插入，即在[1,2]的基础上增加11,112。最后的结果是[],2,1,12,11,112。

	int insertNum = 0;//需要插入num[index]的集合数目
	public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num)
	{
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if(num==null||num.length==0)
			return list;
		Arrays.sort(num);
		return getSubsets(num, 0);
	}
	
	public ArrayList<ArrayList<Integer>> getSubsets(int[] num , int index)
	{
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if(index==num.length-1)
		{
			list.add(new ArrayList<Integer>());
			ArrayList<Integer> number = new ArrayList<Integer>();
			number.add(num[index]);
			list.add(number);
			return list;
		}
		else
		{
			ArrayList<ArrayList<Integer>> tmp = getSubsets(num, index+1);
			ArrayList<Integer> tmpnum ;
			for(int i = 0;i<tmp.size();i++)
			{
				list.add(tmp.get(i));
			}
			for(int i = 0;i<tmp.size();i++)
			{
				if(num[index]==num[index+1])
				{
					//开始插入点分两种情况
					//1.如果说insertNum为0，也就是说一开始就是相同的数字如数组[2,2] 那么在最后一个元素插入即可。2的subset是[],2，那么[2,2]的subset是[],2,22，也就是从2开始插入的
					//2.如果说不为0，那么就是从tmp.size()-insertNum开始插入。如[1,2,2],2的subset是[],2，那么[1,2]的subset是[],2,1,12.此时记录insertNum为[1,2]的长度也就是2.那么[1,1,2]的
					//subset在[1,2]的基础上从tmp.size()-insertNum开始插入，即在[1,2]的基础上增加11,112。最后的结果是[],2,1,12,11,112
					int startIndex = insertNum==0?tmp.size()-1:tmp.size()-insertNum;
						if(i>=startIndex)
						{
							tmpnum = new ArrayList<Integer>(tmp.get(i));
							tmpnum.add(0, num[index]);
							list.add(tmpnum);
						}
				}
				else
				{
					insertNum = tmp.size();
					tmpnum = new ArrayList<Integer>(tmp.get(i));
					tmpnum.add(0, num[index]);
					list.add(tmpnum);
				}
			}
			return list;
		}
	}

Subsets II,布布扣,bubuko.com

Subsets II

原文：http://blog.csdn.net/cow__sky/article/details/21949923