力扣--深度优先算法/回溯算法47.全排列 Ⅱ-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣--深度优先算法/回溯算法47.全排列 Ⅱ。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣--深度优先算法/回溯算法47.全排列 Ⅱ,算法,leetcode,深度优先,数据结构,c++,c语言

思路分析：文章来源地址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模板网！