Subsets

题目原型：

Given a set of distinct integers, 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,3], a solution is:

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

先对数组进行排序，利用递归，总体分为两步（以1、2为例），假设我们已经求出了2的subset，为：[]、2。那么求1、2的subset时：

1、把2的subset加进来[],2
2、把1加到2的subset的第一个位置

	public ArrayList<ArrayList<Integer>> subsets(int[] S)
	{
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if(S==null||S.length==0)
			return list;
		Arrays.sort(S);
		return getSubsets(S, 0);
	}
	
	public ArrayList<ArrayList<Integer>> getSubsets(int[] S , int index)
	{
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if(index==S.length-1)
		{
			ArrayList<Integer> num = new ArrayList<Integer>();
			num.add(S[index]);
			list.add(num);
			list.add(new ArrayList<Integer>());
			return list;
		}
		else
		{
			ArrayList<ArrayList<Integer>> tmp = getSubsets(S, 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++)
			{
				tmpnum = new ArrayList<Integer>(tmp.get(i));
				tmpnum.add(0, S[index]);
				list.add(tmpnum);
			}
			return list;
		}
	}

Subsets,布布扣,bubuko.com

Subsets

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