题解 | #有重复项数字的全排列#

这个链接中是解决没有重复项数字的全排列的思路。此时我的总体递归思想是，取出第一个数字，递归得到剩下list的全排列，然后把第一个数字插入到结果的每一个位置。这样一种递归思想确实能得到全排列，但是当有重复数字时，很难将结果按照字典顺序返回。因为这种递归思想中对于重复数字的解决办法是得到递归结果，然后把递归结果中重复的删除，这样确实可以得到没有重复的结果，但是确不是完全按照字典升序排列的，比如[-1,0,3,3]，再把-1作为开头数字时，返回的全排列是[0,3,3],[3,0,3],[3,3,0],把-1插入时[3,0,3,-1]是在[3,-1,3,0]前面，也就造成问题了。

因此需要换一种递归思路，每次递归时，先遍历每个数字，依次把该数字放在开头，然后得到剩余list的全排列，在拼接即可。如果遇到数字和它后面一个数字相同时，就直接pass即可，这样一种递归也就直接解决了重复数字问题，因此顺序不会出bug。具体算法流程如下：

1. 按照顺序排列list；
2. 遍历list，取出a=list[i],如果a=list[i+1]，那么不递归，否则就递归获取剩余list序列的全排列，把a放在开头拼接即可。

注意一下边界条件就没问题了。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permuteUnique(self , num) :
        # write code here
        if len(num)==1:
            return [num]
        num.sort()
        new_result = []
        for i in range(len(num)-1):
            a = num[i]
            if a == num[i+1]:
                pass
            else:
                result = self.permuteUnique(num[:i]+num[i+1:])
                for j in range(len(result)):
                    new_result.append([a]+result[j])
        a = num[-1]
        result = self.permuteUnique(num[:-1])
        for j in range(len(result)):
            new_result.append([a]+result[j])
        return new_result



num = [-1,3,0,3]
print(Solution().permuteUnique(num))