LeetCode Permutaions II

LeetCode解題之Permutaions II

原題

輸出一個有重復數字的數組的全排列。

注意點：

例子：

輸入: nums = [1, 2, 1]
輸出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

解題思路

這道題是上一題 Permutations 的加強版，現在要考慮重復的數字了，采用了偷懶的辦法，先把數組排序，遍歷時直接無視重復的數字，在原來的基礎上只要添加兩行代碼。

AC源碼

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        self.get_permute([], nums, result)
        return result

    def get_permute(self, current, num, result):
        if not num:
            result.append(current + [])
            return
        for i, v in enumerate(num):
            if i - 1 >= 0 and num[i] == num[i - 1]:
                continue
            current.append(num[i])
            self.get_permute(current, num[:i] + num[i + 1:], result)
            current.pop()


if __name__ == "__main__":
    assert Solution().permuteUnique([1, 2, 1]) == [[1, 1, 2], [1, 2, 1], [2, 1, 1]]