```
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
n = len(nums)
if n == 0:
return []
res = [[nums[0]]]
for i in xrange(1, n):
tmp = res[:] # a shallow copy of 'res'
res = []
# insert nums[i] to each position of each permutation
for j in xrange(i,-1,-1):
res = res + [x[:j]+[nums[i]]+x[j:] for x in tmp]
return res
```