如何用回溯法实现47的全排列II算法？

本文共计561个文字，预计阅读时间需要3分钟。

给定一个包含重复数字的序列，返回所有不重复的全排列。

示例：输入：[1, 1, 2]输出：[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

思路：在生成全排列的基础上，加入去重的逻辑。

具体步骤如下：

1.对输入序列进行排序，确保重复的数字相邻。

2.使用回溯法生成所有可能的排列。

3.在递归过程中，使用一个集合来记录已经使用过的数字，避免重复使用相同的数字。

4.当生成一个排列时，检查是否已经存在相同的排列，如果不存在，则将其添加到结果列表中。

代码实现：

pythondef permute_unique(nums): def backtrack(start, end): if start==end: result.append(nums[:]) return seen=set() for i in range(start, end): if nums[i] in seen: continue seen.add(nums[i]) nums[start], nums[i]=nums[i], nums[start] backtrack(start + 1, end) nums[start], nums[i]=nums[i], nums[start]

nums.sort() result=[] backtrack(0, len(nums)) return result

使用示例：pythonprint(permute_unique([1, 1, 2]))

输出：[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

给定一个可包含重复数字的序列，返回所有不重复的全排列。示例:输入:[1,1,2]输出:[[1,1,2],[1,2,1],[2,1,1]]思路：在全排列I的基础上，加上去重即可怎么去

给定一个可包含重复数字的序列，返回所有不重复的全排列。示例:输入: [1,1,2]输出:[ [1,1,2], [1,2,1], [2,1,1]]

思路：在全排列I的基础上，加上去重即可

怎么去重：先把数组进行排序，然后在放到临时数组时，如果数组的前一个数和当前数一样且前一个数还没放过，则跳过这个数的放入

效率：30.18%

class Solution {public: int nums_size; vector res; vector temp; vector is_visit; void put_in(vector } else { for (int i = 0; i 0 is_visit[i] = true; temp.push_back(nums[i]); put_in(nums); temp.pop_back(); is_visit[i] = false; } } } } vector permuteUnique(vector nums_size = nums.size(); is_visit.resize(nums_size, false); put_in(nums); return res; }};