```
class Solution(object):
def permute(self, nums):
if len(nums) == 0:
return [[]]
if len(nums) == 1:
return [nums]
permuted = self.permute(nums[1:])
out = []
for each in permuted:
for i in range(len(permuted[0])+1):
l = list(each)
l.insert(i,nums[0])
out.append(l)
return out
```