1
# Runtime: 136 ms (Top 31.20%) | Memory: 14.2 MB (Top 62.53%)
2
class Solution(object):
3
    def permuteUnique(self, nums):
4
        """
5
        :type nums: List[int]
6
        :rtype: List[List[int]]
7
        """
8
        if len(nums) == 1:
9
            return [[nums[0]]]
10

11
        res = self.permuteUnique(nums[1:])
12

13
        for i in range(len(res) - 1, -1, -1):
14
            j = 0
15
            while j < len(res[i]):
16
                if res[i][j] == nums[0]:  # to account for repeated nums
17
                    break
18
                lst = res[i][:]
19
                lst.insert(j, nums[0])
20
                res.append(lst)
21
                j += 1
22

23
            res[i].insert(j, nums[0])
24

25
        return res