Can someone help me figure out the dead loop? It runs forever...


  • 0
    public static ArrayList<ArrayList<Integer>> permute(int[] num) {
            ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
            
            int len=num.length;
            boolean[] boo=new boolean[len];
            ArrayList<Integer> list=new ArrayList<Integer>();
            
            return permutation(result, list,num,boo,0);
        }
        
    public static ArrayList<ArrayList<Integer>> permutation(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list, int[] num,boolean[] boo,int index){   
    	if(index==num.length){  //when index ==length, every number has added to the list, so add to result and return
    	    result.add(list);
    	    return result;
    	}
        
        for(int i=0;i<boo.length;i++){
            if(boo[i]==false){
                ArrayList<Integer> copyList=new ArrayList<Integer>();  //copy ArrayList
                for(int j=0;j<list.size();i++)
                    copyList.add(list.get(j));
                    
                boolean[] booCopy=new boolean[boo.length];               //copy boolean array
                for(int k=0;k<boo.length;k++)
                    booCopy[k]=boo[k];
                
                copyList.add(num[i]);                                  //add a number to the list
                booCopy[i]=true;                                         //set that position to visited
                permutation(result,copyList,num,booCopy,index+1);    //pass the copied array and boolean to next recursive call
            }
        }
        
        return result;
    }

  • 2
    M

    Your problem occurs in this segment of code, on lines 19-20 of what you've provided.

    for(int j=0;j<list.size();i++)
      copyList.add(list.get(j));
    

    You are incrementing i, not j. Since j is not increasing, it runs infinitely until you run out of memory.

    Switch to one of the following corrections:

    for(int j=0;j<list.size();j++)
      copyList.add(list.get(j));
    

    while(copyList.size()<list.size())
      copyList.add(list.get(copyList.size()));
    

    ArrayList<Integer> copyList = list.clone();
    

    copyList.addAll(list);
    

    There are other ways to copy an ArrayList, but I just added a few to get my answer length long enough to allow submission.


  • 0
    S

    Thank you, Mike. You answered my questions every time. It passes after I change that j to i.


  • 0
    G

    good point. i am also working on this point


  • 0
    M

    Just a few off topic suggestions:

    1. To copy the array list, you can also pass "list" as an argument to the ArrayList constructor when are creating a new array list. This is another way of copying.
    2. If you do booCopy[i]=false after the recursive call then there will no need to copy booCopy and pass it around. Essentially, you are marking the element at index i before the recursive call and unmarking it after the recursive call.

Log in to reply
 

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