# Recursion solution but get LTE.

• ``````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.

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