2014年4月19日 星期六

[LeetCode] Subsets

Problem:
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: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;
    }
}

沒有留言:

張貼留言