LeetCode : Subset I

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.

Input:[4,1,0]
Expected:[[],[0],[1],[4],[0,1],[0,4],[1,4],[0,1,4]]


public class Solution {
    
    // we do it recursively
    public void pickSS(ArrayList<ArrayList<Integer>> list, int[] remain)
    {
        if(remain==null)return;
        int rl=remain.length;
        if(rl==0) return;
        
        // seperate the list f + remain2
        int f=remain[0];
        int[] remain2=new int[rl-1];
        for(int i=0;i<rl-1;i++){
            remain2[i]=remain[i+1];
        }
        
        ArrayList<ArrayList<Integer>> templist = new ArrayList<ArrayList<Integer>>();

        // templist is addition list
        for(ArrayList<Integer> al:list)
        {
            ArrayList<Integer> nl=new ArrayList<Integer>(); //new list
            int all=al.size();
            if(all==0)
            {
                nl.add(0,f);
                templist.add(nl);  // empty list + one element f
            }
            else
            {
                for(int i=0;i<all;i++)
                    nl.add(i,(Integer)al.get(i));
                nl.add(all,f);
                templist.add(nl);   // joining a list + one element f.
            }
        }

        // result list = original list + temp list
        for(ArrayList<Integer> al:templist)
        {
            list.add(al);
        }
        
        // call next level
        pickSS(list,remain2);
    }

    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        res.add(new ArrayList<Integer>());
        
        //sort S
        for(int i=0;i<S.length;i++)
        {
            for(int j=i+1;j<S.length;j++)
            {
                if(S[j]<S[i])
                {
                    int t=S[i];
                    S[i]=S[j];
                    S[j]=t;
                }
            }
        }
        pickSS(res, S);
        return res;
    }
}