leetcode Subsets

Subsets原題位址：

https://oj.leetcode.com/problems/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],
  []
]      

S中沒有重複元素，将S排序後，每個元素有兩種選擇，取，或者不取。

public class Solution {
    private List<List<Integer>> ans = new LinkedList<List<Integer>>();
	public List<List<Integer>> subsets(int[] S) {
		if (S == null || S.length == 0)
			return ans;
		LinkedList<Integer> temp = new LinkedList<Integer>();
		Arrays.sort(S);
		search(temp, S, 0);
		return ans;
	}
	
	private void search(LinkedList<Integer> temp, int[] S, int idx) {
		if (idx == S.length) {
			LinkedList<Integer> list = (LinkedList<Integer>) temp.clone();
			ans.add(list);
			return;
		}
		temp.add(S[idx]);
		search(temp, S, idx+1);
		temp.pollLast();
		search(temp, S, idx+1);
	}
}