文章来源:https://www.toymoban.com/news/detail-839346.html
思路分析:文章来源地址https://www.toymoban.com/news/detail-839346.html
- 使用DFS算法进行全排列,递归地尝试每个可能的排列方式。
- 使用
path
向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。 - 使用
numvisited
向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。 - 在递归过程中,对于每个未访问的数字,将其加入排列,标记为已访问,然后递归生成下一个位置的数字。
- 在递归完成后,需要回溯,撤销对当前数字的标记,同时将其从排列中移除,以尝试其他可能的排列。
- 使用额外的
visited
向量标记每个数字是否已经在当前排列中被访问过,避免重复访问。
class Solution {
vector<vector<int>> result; // 存储最终的全排列结果
vector<int> path; // 存储当前正在生成的排列
// 深度优先搜索函数,生成全排列
void dfs(vector<int>& nums, vector<bool> numvisited) {
vector<bool> visited(21, false); // 用于标记数字是否被访问过
for (int i = 0; i < nums.size(); i++) {
// 如果当前数字已经在当前排列中使用过,则跳过
if (numvisited[i] == true)
continue;
path.push_back(nums[i]); // 将当前数字加入排列
numvisited[i] = true; // 标记当前数字为已访问
// 如果当前排列长度等于数组长度,说明已经生成一个完整的排列,加入结果集
if (path.size() == nums.size())
result.push_back(path);
// 如果当前数字在当前排列中未被访问过,则递归生成下一个位置的数字
if (visited[nums[i] + 10] != true) {
visited[nums[i] + 10] = true;
dfs(nums, numvisited);
}
path.pop_back(); // 回溯,将当前数字从排列中移除
numvisited[i] = false; // 回溯,撤销对当前数字的标记
}
visited.clear(); // 清除标记数组,节约空间。
}
public:
// 主函数,用于生成给定数组的全排列(包含重复元素)
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> numvisited(nums.size(), false); // 初始化数字访问标记数组
dfs(nums, numvisited); // 调用深度优先搜索函数生成全排列
return result; // 返回最终结果
}
};
到了这里,关于力扣--深度优先算法/回溯算法47.全排列 Ⅱ的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!