[LeetCode]47 全排列 II

题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        ret = [nums.copy()]
        sz = len(nums)

        def nextP():
            prev = sz-1
            while True:
                next = prev
                prev -= 1
                if nums[prev] < nums[next]:
                    cursor = sz-1
                    while nums[cursor] <= nums[prev]:
                        cursor -= 1
                    nums[cursor], nums[prev] = nums[prev], nums[cursor]
                    nums[next:] = nums[sz-1:prev:-1]
                    return True
                if prev == 0:
                    return False
        if sz > 1:
            while nextP():
                ret.append(nums.copy())
        return ret