Recursion solution but get LTE.


  • 0
    T
    public class Solution {
    List<List<Integer>> L=new LinkedList<List<Integer>>();
    public int[] SS;
    public List<List<Integer>> subsets(int[] S) {
        List<Integer> l=new LinkedList<Integer>();
        L.add(l);
        if(S.length==0) return L;
        SS=sort(S,0,S.length-1);
        int x=0;
        findSub(x,l,SS);
        return L;
    }
    
    void findSub(int x,List<Integer> l,int[] SS){
        if(x<0 || x>=SS.length) return;
        findSub(x+1,l,SS);
        l.add(SS[x]);
        L.add(l);
        findSub(x+1,l,SS);
    }
    
    int[] sort(int[] s,int head,int tail){
        //mergesort
        if(head==tail) return Arrays.copyOfRange(s,head,head+1);
        int mid=(head+tail)/2;
        int[] left=sort(s,head,mid);
        int[] right=sort(s,mid+1,tail);
        int[] tmp=new int[s.length];
        int i=0;
        int j=0;
        while(head<=tail){
            if(i>=left.length){
                tmp[head]=right[j];
            }else if(j>=right.length){
                tmp[head]=left[i];
            }else{
                if(left[i]<right[j]){
                    tmp[head]=left[i];
                    i++;
                }else{
                    tmp[head]=right[j];
                    j++;
                }
            }
            head++;
        }
        return tmp;
    }
    

    }

    Sort the array first (O(nlogn)), and find all subset (O(n)). How can I improve it? I suppose there are some redundant part which causes LTE.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.