```
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> cur = new ArrayList<List<Integer>>();
List<List<Integer>> prev = new ArrayList<List<Integer>>();
prev.add(new ArrayList<Integer>(Arrays.asList(nums[0])));
for (int i = 1; i < nums.length; i++){
for (List<Integer> list: prev){
for (int j = 0; j <= list.size(); j++){
list.add(j, nums[i]);
cur.add(new ArrayList<Integer>(list));
list.remove(j);
}
}
prev = cur;
cur = new ArrayList<List<Integer>>();
}
return prev;
}
```

The idea is that the permutation of case (i) can be achieved by inserting nums[i] into all possible spots of all permutation of case(i - 1).

For example, [1, 2] has two permutations [1, 2] and [2, 1].

The permutation of [1, 2, 3] can be achieved by inserting 3 into every possible spot of [1, 2] and [2, 1]. Then for [1, 2], we can have [3,1, 2], [1, 3, 2], and [1, 2, 3]. For [2, 1], we can have [3, 2, 1], [2, 3, 1], and [2, 1, 3].