1. 题目解析
题目链接:47. 全排列 II
这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。
2.算法原理
算法思路梳理
为了生成给定数组nums
的全排列,同时避免由于重复元素导致的重复排列,我们可以遵循以下步骤和策略:
- 预处理与排序
- 由于题目不要求返回排列的顺序,我们可以首先对
nums
进行排序,使得所有相同的元素相邻。这样方便后续操作,因为我们可以根据元素的顺序来避免产生重复的全排列。
- 由于题目不要求返回排列的顺序,我们可以首先对
- 定义递归函数
- 设计一个递归函数
backtrack(vector<int>& nums, int idx)
,其中idx
表示当前需要填充的位置。该函数用于搜索并存储所有合理的排列。
- 设计一个递归函数
- 初始化数据结构
- 使用一个二维数组
ans
来存储所有可能的排列。 - 使用一个一维数组
perm
来保存当前状态下的排列。 - 使用一个一维数组
visited
来标记元素是否已经被选择用于当前排列。
- 使用一个二维数组
- 递归过程
- 递归终止条件:当
idx
等于nums
的长度时,说明已经处理完所有数字,此时将perm
数组加入ans
。 - 递归状态转移:对于每个下标
i
,如果nums[i]
未被标记(即visited[i]
为0),并且如果它之前的相同元素(如果存在)已被标记,则执行以下步骤:- 标记
visited[i]
为1,表示nums[i]
已被选择用于当前排列。 - 将
nums[i]
添加到perm
数组的末尾。 - 递归调用
backtrack
函数,处理下一个位置(即idx+1
)。 - 递归返回后,进行回溯操作:将
visited[i]
重新设为0,并从perm
数组中移除nums[i]
。
- 标记
- 递归终止条件:当
- 注意事项
- 在选择元素时,必须确保相同元素按照它们在排序后数组中的顺序出现在排列中。这样可以确保不会产生重复的全排列。
- 如果当前元素之前的相同元素未被选择(即未被标记),则当前元素也不能被选择,这同样是为了避免重复排列。
- 返回结果
- 递归完成后,
ans
数组将包含所有不重复的全排列。
- 递归完成后,
算法实现细节
- 在递归函数中,需要仔细处理边界条件和状态转移的逻辑,确保每次递归调用都符合题目要求。
- 使用
visited
数组可以有效地避免重复选择相同的元素,尤其是在处理含有重复元素的数组时。 - 回溯操作是深度优先搜索中的重要步骤,它允许我们撤销之前的选择,并尝试其他可能性。
3.代码编写
class Solution {vector<int> path;vector<vector<int>> ret;bool cheak[9];
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){//剪枝是重点,if判断!!!if(cheak[i] == true || (i != 0 && nums[i] == nums[i - 1]) && cheak[i - 1] == false){continue;}path.push_back(nums[i]);cheak[i] = true;dfs(nums, pos + 1);path.pop_back();cheak[i] = false;}}
};
The Last
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~