Permutation II

题目描述

解题方法

Solution

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        if not nums:
            return results
        length = len(nums)
        nums.sort()
        used = [False for i in range(length)]
        self.permuteHelper(nums, used, results, [])
        return results

    def permuteHelper(self, nums, used, results, curList):
        if len(curList) == len(nums):
            tmpList = list(curList)
            results.append(tmpList)

        for i in range(len(nums)):
            if i != 0 and nums[i] == nums[i-1] and used[i-1] == False:
                #当i不等于0, nums[i] == nums[i-1]还不够成跳过条件
                #如果前一个number已经用在这个list里，是应该保留这个结果的
                #只有当前一个number没有被用，如果再用这个重复的数，就会duplicate
                #所以加上 used[i-1] == False
                continue
            if not used[i]:
                curList.append(nums[i])
                used[i] = True
                self.permuteHelper(nums, used, results, curList)
                curList.pop()
                used[i] = False

Reference