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 =
If S =
[1,2,3]
, a solution is:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]Solution:O(n)
public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { Arrays.sort(S); ArrayList<ArrayList<Integer>> list = new ArrayList<>(); if(S == null || S.length == 0) return list; if(S.length == 1){ list.add(new ArrayList<Integer>()); ArrayList<Integer> t1 = new ArrayList<>(); t1.add(S[0]); list.add(t1); } int S1 [] = Arrays.copyOfRange(S,0,S.length-1); ArrayList<ArrayList<Integer>>slist = subsets(S1); for(ArrayList<Integer>l:slist) list.add(l); for(ArrayList<Integer>l:slist){ ArrayList<Integer> t = new ArrayList<Integer>(l); t.add(S[S.length-1]); list.add(t); } return list; } }
沒有留言:
張貼留言