47. Permutations II

# 09:19 -- 09:51
# run time: 129ms, 28%; 109ms, 59%; 138ms, 22%
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort ()
        lens = len(nums)
        if lens == 1:
            return [nums]
        if lens == 0:
            return nums
        if lens == 2:
            if nums[0] == nums[1]:
                #print nums, nums
                return [nums]
            else:
                #print [[nums[0], nums[1]], [nums[1], nums[0]]], nums
                return [[nums[0], nums[1]], [nums[1], nums[0]]]
        else:
            output = []
            for i in xrange(lens):
                if i == 0:
                    temp_nums = nums[1:]
                    result = self.permuteUnique (temp_nums)
                    if type(result[0]) != type(1):
                        for x in result:
                            output.append( [nums[i]] + x)
                    else:
                        output.append ([nums[i]] + result)
                elif nums[i] == nums[i - 1]:
                    continue
                else:
                    if i == lens:
                        temp_nums = nums[:-1]
                    else:
                        temp_nums = nums[:i] + nums[i+1 :]
                    result = self.permuteUnique (temp_nums)
                    if type(result[0]) != type(1):
                        for x in result:
                            output.append( [nums[i]] + x)
                    else:
                        output.append ([nums[i]] + result)
            #print output, nums
            return output