Time Limited Exceeded


  • 0
    J

    Hi,

    Here is my idea to implement the permutation:
    before:{1,2}{2,1}
    insert 3:
    {3,1,2},{1,3,2},{1,2,3}
    {3,2,1},{2,3,1},{2,1,3}

    From above, in order to get permutation of {1,2,3}, i firstly got permutation of {1,2}, and insert 3 into them. So the problem can be solved by using recursion.

    However when I implemented with recursion, I got time limited exceeded. So I was trying to solve it by turning recursion into dynamic programming. However, I still Time Limited Exceeded.

    Below is my code, can anyone help me to change it into a appropriate form of DP.

    public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        int size=num.length;
        if(size==0)
            return result;
        if(size==1){
            ArrayList<Integer> item=new ArrayList<Integer>();
            item.add(num[0]);
            result.add(item);
            return result;
        }
        
        permute(num,size,result);
        return result;
    }
    
    public void permute(int[] num, int size, ArrayList<ArrayList<Integer>> result){
        int k=1;
        ArrayList<Integer> item=new ArrayList<Integer>();
        item.add(num[0]);
        result.add(item);
        
        while(k<size){
            int r_size=result.size();
            for(int i=0;i<r_size;i++){
                ArrayList<Integer> base=result.remove(i);
                for(int j=0;j<k+1;j++){
                    ArrayList<Integer> current=base;
                    current.add(j,num[k]);
                    result.add(current);
                }
            }
            k++;
        }
     }
    

    }


Log in to reply
 

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