leetcode代码记录（全排列 II

1. 题目：

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

示例 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]]

2. 我的代码：

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:# 回溯path = []result = []def backtracking(rest):# 终止条件if rest == []:result.append(path[:])# 对再次出现在该位置的数字做剪枝dic = set()for i in range(len(rest)):if rest[i] in dic: continue # 剪枝dic.add(rest[i])path.append(rest[i])backtracking(rest[:i] + rest[i + 1:])path.pop()backtracking(nums)return result

这个题继续使用回溯算法，只不过要配合剪枝操作。在每一层定义一个set作为遍历过的元素的记录，如果不在记录中则可以递归，如果在记录中则直接剪枝，continue。

为什么要剪枝呢，因为如果相同元素在次位置再递归一次，则会产生和之前递归过的一模一样的分支。继续将遍历完整个列表作为终止条件即可。

以树形结构展示为下图：

小结：

关注我给大家分享更多有趣的知识，以下是个人公众号，提供 ||代码兼职|| ||代码问题求解||
添加我的公众号即可：