Subsets (Java)

Leetcode

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

Solution: DFS

For  subset of a given set, it must contain a [],
So we can initialize a result with [[]] as start point.  For example, given set [1,2,3]
We can build the result from [[]]-> [[],[1]]->[[],[1],[2],[1,2]]->[[],[1],[2], [1,2], [3], [1,3], [2,3], [1, 2,3]]

	/*
	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],
	[]
	]
	*/
	public class Solution {
	public ArrayList<ArrayList<Integer>> subsets(int[] S) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (S==null|| S.length==0){
	return result;
	}
	Arrays.sort(S);
	// start point to build all the subsets
	ArrayList<Integer> temp=new ArrayList<Integer>();
	result.add(temp);
	for (int i=0; i<S.length; i++){
	insert(S[i], result);
	}
	return result;
	}
	private void insert(int i, ArrayList<ArrayList<Integer>> result){
	ArrayList<ArrayList<Integer>> tempResult=new ArrayList<ArrayList<Integer>> ();
	for (ArrayList<Integer> current: result){
	ArrayList<Integer> temp=new ArrayList<Integer> (current);
	temp.add(i);
	tempResult.add(temp);
	}
	result.addAll(tempResult);
	}
	}

view raw Subsets.java hosted with ❤ by GitHub