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++;
}
}
```

}