LeetCode 47. 全排列 II

题目

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

例：
输入：nums = [1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1]]

方法：回溯、递归

思路类似 46. 全排列，不同之处在于本题数组 nums 中可能存在重复元素值

• path 表示单一的排列方式，result 表示所有可能的排列方式。use 表示数组中的元素是否已被使用，1 表示已被使用，0 表示未被使用
• 因为可能存在元素值相同的情况，所以需要对数组 nums 进行排列

backtrack 函数：回溯

• 因为对数组进行排列，那么 path 内包括所有 nums 元素时，即 path 的长度等于 nums 的长度，完成一次排列，将其加入 result
• 因为首位为不同元素表示不同的排列方式，所以每层的循环都是从零开始。但是由于不能重复使用同一元素，那么需要对元素是否使用过进行判断，当选取的元素并未使用过时，即 use[i] = 0，才可继续
• 若选取的元素并非数组 nums 的第一个元素，且该元素与前一个元素的值相同，且前一个元素在该 path 中并未使用，由于每次的循环都是从零开始，即选取元素的前一个元素 nums[i-1] 已实现过和该元素相同的排列，那么跳过此次循环
  例：下图的树的第二层，当第一个数均为 1 时，第二个可以被剪枝
  

class Solution(object):
    def permuteUnique(self, nums):
        path, result = [], []
        use = [0] * len(nums)
        nums.sort()

        def backtrack(nums):
            if len(path) == len(nums):
                result.append(path[:])
                return None

            for i in range(len(nums)):
                if not use[i]:
                    if i > 0 and nums[i-1] == nums[i] and not use[i-1]:
                        continue
                    use[i] = 1
                    path.append(nums[i])
                    backtrack(nums)
                    path.pop()
                    use[i] = 0

        backtrack(nums)
        return result

参考

代码相关：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html