permutations (全排列)

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        if len(nums) ==1:
            return [nums]
        
        first = nums[0]
        nums = nums[1:]
        
        last_ret = self.permute(nums)
        
        new_ret = []
        
        for x in last_ret:
            for i in range(len(x)+1):
                x.insert(i, first)
                new_ret.append(x[:])
                del(x[i])
                
        return new_ret