全排列II

Leetcode Link: 47. 全排列 II - 力扣（LeetCode）

题目

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

解法一

思路： 本题同样属于回溯中的排列问题，而和全排列问题相比，本题输入中有重复数字。因此涉及到了去重的问题。

类似的，本题的去重实际上也是在树的同一层去重，因此可以使用 last_val==val 来进行去重

然而，本题中还有另外一个难点，就是如何判定一个重复的数字，在同一棵子树上（不是同一层了）被用了多少了，左到“不多用，不少用”。

可以用一个字典来记录出现的所有元素以及他们的出现次数，每次拿到一个 val，判定需不需要去重，并通过查询字典获知“还能用多少次”，如果还能用 0 次，就说明该元素不能再被使用了，就 continue

满足题目条件：

1. 到达叶子节点，即 len(path)==len(nums)

停止回溯条件：

1. 无特殊停止回溯条件，满足题目条件时可以停止回溯

去重&剪枝

1. last_val 的同层去重
2. 每个 val 使用次数查询，如果可使用次数 =0，同样需要 continue

题解：

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtracking():
            nonlocal res, path, nums, lookup
            # 停止回溯条件
            # 满足题目要求
            if len(path) == len(nums):
                res.append(path.copy())
                return
            
            last_val = float('inf')
            for val in nums:
		        # 去重和剪枝，后一个判断是查询当前值还能使用几次
                if val == last_val or lookup[val] == 0:
                    continue
                last_val = val
                # 注意同时维护path和val的可使用次数
                path.append(val)
                lookup[val] -= 1
                backtracking()
                path.pop()
                lookup[val] += 1
 
        res = []
        path = []
        nums. sort () # 一定要排序
        # 制作每个值可使用次数的查询字典
        lookup = collections.defaultdict(int)
        for val in nums:
            lookup[val] += 1
        backtracking()
        return res
 

对于上面代码中 lookup 的数据结构，也可以使用一个和nums同等长度的列表来记录，这样表示的就是对应位置的数值有没有被用过，用过了就是1，没用过就是0

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtracking():
            nonlocal res, path, nums, lookup
            if len(path) == len(nums):
                res.append(copy.deepcopy(path))
                return
            
            last_val = float('inf')
            for idx, val in enumerate(nums): # 这里要稍微改一下
                if val == last_val or lookup[idx] == 1:
                    continue
                last_val = val
                path.append(val)
                lookup[idx] = 1 # 用0或者1来指示有没有用过
                backtracking()
                path.pop()
                lookup[idx] = 0
 
        res = []
        path = []
        nums.sort()
        lookup = [0]*len(nums) # 这里是列表了
        backtracking()
        return res

解法二

思路：复习的时候写的代码

直接用pop和append来控制就行，因为是在同一个循环内进行的这两种操作，所以for的时候不会由于choose的长度变化报错。

题解：

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        nums.sort()
        def backtracking(choose):
            if choose == []:
                res.append(path.copy())
            
            last_num = -float('inf')
            for i in range(len(choose)):
                if choose[i] != last_num:
                    last_num = choose[i]
                    cur_num = choose[i]
                    path.append(choose[i])
                    choose.pop(i)
                    backtracking(choose)
                    path.pop()
                    choose.insert(i, cur_num)
            
        backtracking(nums)
        return res
 

解法三

思路：

题解：

启发和联系