题目描述

给出一个具有重复数字的列表，找出列表所有不同的排列。

测试样例

输入：[1,1]

输出：

[

  [1,1]

]

输入：[1,2,2]

输出：

[

  [1,2,2],

  [2,1,2],

  [2,2,1]

]

解题思路

使用递归DFS，拿出一个数字加入排列中，然后与剩下的数字做组合。这里的关键在于去重！需要先将数字序列进行排序，然后标记每个位置的数字是否在已当前的排列方案中，每次DFS前先将该位置进行标记，DFS完后再取消标记，以便后面的数字可以与前面的数字做组合。

在DFS过程中，若当前位置的数字已标记或者当前位置的数字与前一个位置的数字相同，同时前一个位置未标记，则跳过。这里或许需要多想一下，为什么需要“前一个位置未标记”这个条件？

前面提到过，每个位置的数字在其DFS完后会取消对应的标记，于是“前一个位置未标记”就代表当前位置的数字在此刻的排列方案中排在了前一个位置的数字前面，而这种方案肯定已被前一个数字的DFS过程给覆盖了，于是可直接跳过，不必进行重复处理。

代码

class Solution:

    """

    @param: :  A list of integers

    @return: A list of unique permutations

    """

    def permuteUnique(self, nums):

        result = []

        # 记录每个位置的数字是否在当前排列中已使用

        in_use = [False] * len(nums)

        # 注意将nums排序

        self.dfs(sorted(nums), [], result, in_use)

        return result

    def dfs(self, nums, tmp, result, in_use):

        if len(tmp) == len(nums):

            result.append(tmp)

            return

        for i, n in enumerate(nums):

            # 若当前位置的数字已在排列当中，则跳过；

            # 或者当前位置的数字作为排列的第一个数字

            # 且与前一个位置的数字相同时，也跳过

            # 这里in_use[i - 1]为False说明当前位置的数字

            # 在当前的排列方案中排列在前一个位置的数字前，

            # 否则若前一个位置的数字排列在当前位置的数字前的话，

            # in_use[i - 1]绝对为True

            if in_use[i] or (i and n == nums[i - 1] and not in_use[i - 1]):

                continue

            in_use[i] = True

            self.dfs(nums, tmp + [n], result, in_use)

            in_use[i] = False