Why my base case seems very different than the solution from others? and memory consume too much?


  • 0
    A
    public class Solution 
    {
    
    public List<List<Integer>> permute(int[] num)
    {
    
            if (num.length==0) return null;
             
            List<List<Integer>> A=new ArrayList<List<Integer>>();//Why outter level is ArrayList and inner is List
            
            //base case
            if (num.length==1){
                ArrayList<Integer> a=new ArrayList<Integer>();
    	        a.add(num[0]);
    	        A.add(a);
    	        return A;
            }
            
            
            for (int i=0;i<num.length; i++)
            {
                    int x=num[i];
                    
                    //generate the a sub Num array without current used character;
                    int[] subNum=new int[num.length-1];
                    for (int k=0;k<num.length-1;k++)
                    {
                        if (k<i) subNum[k]=num[k];
                        else subNum[k]=num[k+1];
                    }
                    
                    //call permute with subNum
                    List<List<Integer>> B=permute(subNum);
                    
                    //add x to the front of each element of B
                    for (int j=0;j<B.size();j++)
                    {
                           B.get(j).add(0, x);
                    }
                    
                    //add B back to A
                    A.addAll(B);
    					
    	    }
    	    
    	    return A;
        }
    }

Log in to reply
 

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