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 public class Solution { 2 public ArrayList<ArrayList<Integer>> subsets(int[] S) { 3 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 4 ArrayList<Integer> output = new ArrayList<Integer>(); 5 Arrays.sort(S); 6 res.add(new ArrayList<Integer>()); 7 DFS(S,0,output,res); 8 return res; 9 } 10 11 public void DFS(int[] S,int start, ArrayList<Integer>output,ArrayList<ArrayList<Integer>>res){ 12 for(int i=start;i<S.length;i++){ 13 output.add(S[i]); 14 ArrayList<Integer> temp = new ArrayList<Integer>(); 15 temp.addAll(output); 16 res.add(temp); 17 DFS(S,i+1,output,res); 18 output.remove(output.size()-1); 19 } 20 } 21 }