[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Then, 2 can be added in front or after 1. So we have to copy the List<Integer> in answer (it's just {1}), add 2 in position 0 of {1}, then copy the original {1} again, and add 2 in position 1. Now we have an answer of {2,1},{1,2}. There are 2 lists in the current answer.

Then we have to add 3. first copy {2,1} and {1,2}, add 3 in position 0; then copy {2,1} and {1,2}, and add 3 into position 1, then do the same thing for position 3.

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        List<Integer> l0 = new ArrayList<Integer>();
        if(nums==null || nums.length==0)
            return ret;
        l0.add(nums[0]);
        ret.add(l0);

        for(int i=1;i<nums.length;i++){
            List<List<Integer>> new_ret = new ArrayList<List<Integer>>();
            // j: new pos
            for(int j=0;j<=i;j++){
                // each list in ret
                for(List<Integer>l: ret){
                    // copy list
                    List<Integer> new_l = new ArrayList<Integer>(l);
                    new_l.add(j,nums[i]);
                    new_ret.add(new_l);
                }
            }
            ret = new_ret;
        }

        return ret;
    }
}

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = []
        if not nums:
            return ret
        self.recP(nums,ret,[])
        return ret
    def recP(self,nums,ret,tmp):
        if len(nums) == 0:
            ret.append(tmp[:])
            return
        for i,j in enumerate(nums):
            tmp.append(j)
            nums.pop(i)
            self.recP(nums,ret,tmp)
            tmp.pop()
            nums.insert(i,j)