Python每日一练-----全排列Ⅱ
⛅（day23）
目录
🖍题目：
题目分析：
🌈回溯解法
✏代码注释
没看过全排列Ⅰ可先看看全排列Ⅰ，更好理解全排列Ⅱ
Python每日一练-----全排列（回溯思想）_亖夕的博客-CSDN博客
🖍题目：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
（1 <= nums.length <= 8）
🌠示例 1:
输入：nums = [1,1,2]
输出： [[1,1,2], [1,2,1], [2,1,1]]
🌠示例 2:
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
题目分析：
题目要求对给出的数组的数值进行全排列，因为列表中可能含有重复元素，所以在全排列的过程中去重是重点。
解题思路：
和全排列Ⅰ不同的是，这里所给的列表nums可能包含有重复的数字。我们就需要使用其他的列表来记录已填写的数字，所以我们在这不用交换的方法填入数字，使用逐个填入的方法。
这是一种暴力解题的形式，但是不是说暴力解题时间，空间复杂度都比较高吗？
确实是这样，但是对于一些题目能用暴力解题解决已经很不错了对于全排列的类型，仅仅单靠暴力解题常用的for循环也是比较难写的。
我们可以采取逐个填入的方法获得不同的排列。把列表nums看成n个空位置，从头开始不断填入一位数字，对于填到第几个位置我们可以使用 i 记录，这样当 i = n时，说明n个空位已经填完，我们就可以将第一个结果添加进结果列表，接着进行下一个结果的计算。
但是为了解决重复的问题，我们需要判断什么时候可以填入该数字，什么时候重复了不可以填入。
例如[1, 1, 2]，如果没有去重操作直接进行全排列有以下结果。
[1, 1, 2], [1, 2, 1],第一个位置放第一个1
[1, 1, 2], [1, 2, 1],第一个位置放第二个1
[2, 1, 1], [2, 1, 1],第一个位置放2
那么我们要进行去重操作就需要指定一个判断条件，指出什么时候可以填入该数字，什么时候重复了不可以填入。
首先将列表nums用sort()排列，这样列表含有重复数字就会相邻在一起，这时我们再判断该数字填入是否满足不构成重复的条件。
那么这个条件可以是j > 0 and nums[j] == nums[j - 1] and not vis[j - 1].其中的 vis是用于记录已填写数字的列表。这样就可以保证当含有重复数字时，同一个位置只取重复数字的第一个数填入该空。
图解（来自代码随想录）
利用排好序的nums，根据nums[j - 1] = nums[ j ]判断列表nums中是否有重复的数字，若有则根据vis列表判断填入是否构成重复数组。
代码实现
🌈回溯解法
def permuteUnique(nums): def backtrack(i): if i == n: res.append(curres[:]) else: for j in range(n): if not used[j]: if j > 0 and nums[j] == nums[j - 1] and not used[j - 1]: continue used[j] = 1 curres.append(nums[j]) backtrack(i + 1) used[j] = 0 curres.pop() nums.sort() n = len(nums) res = [] curres = [] used = [0] * n backtrack(0) return res✏代码注释
def permuteUnique(nums): def backtrack(i): if i == n: # 填入完成 res.append(curres[:]) # 添加进结果列表 else: for j in range(n): if not used[j]: if j > 0 and nums[j] == nums[j - 1] and not used[j - 1]: continue used[j] = 1 # 将used对应的位置由0赋值为1，表示该位置已填入 curres.append(nums[j]) backtrack(i + 1) # 递归结束后撤回操作 used[j] = 0 curres.pop() nums.sort() # 对nums进行排序 n = len(nums) res = [] curres = [] used = [0] * n # 初始化used列表 backtrack(0) return res今天就到这，明天见。🚀
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄