力扣第47题 全排列 || c++ 回溯 双层去重 思路+注释

题目

47. 全排列 II

中等

相关标签

数组   回溯

给定一个可包含重复数字的序列 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]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

思路和解题方法

1. 首先定义了两个成员变量 result 和 path，用于保存最终的结果和当前的路径。
2. backtracking 函数是核心的回溯函数，用于生成所有的排列。在每一轮回溯中，需要遍历每个位置可能的选择，即遍历数组中的每个元素。
3. 为了排除重复的情况，使用了剪枝操作。通过对原数组进行排序，相同的元素会相邻出现。在遍历过程中，如果发现当前元素与前一个元素相同，并且前一个元素还未被使用过（即 used[i-1] 为false），说明这是同一树层的重复元素，直接跳过继续遍历下一个元素。
4. 如果元素没有重复且未被使用，则将其标记为已使用，加入到当前路径中，然后递归调用 backtracking 函数以继续生成下一个位置的选择。递归完成后，需要进行回溯操作，即将当前元素从路径中去除，并将其状态标记为未使用，以便在后续的遍历中可以选择该元素。
5. 最终，在回溯过程中找到了一组完整的排列，将其加入到结果集 result 中。
6. 在主函数 permuteUnique 中，首先进行了初始化操作，清空结果集和路径，并对原数组进行排序。然后调用 backtracking 函数生成所有的排列。最后返回最终的结果。

复杂度

        时间复杂度:

                O(n! * n)

• 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组

        空间复杂度

                O(n)

•  空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素

c++ 代码

class Solution {
private:
    vectorint>> result; // 存储所有排列结果的二维数组
    vector<int> path; // 当前正在构造的排列
 
    /**
     * 回溯函数，用于生成排列
     * @param nums 给定数组
     * @param used 标记数组，记录每个元素是否已经被使用
     */
    void backtracking(vector<int> &nums, vector<bool> &used) {
        if (path.size() == nums.size()) { // 当前排列的长度等于给定数组的长度，已经生成了一个完整的排列
            result.push_back(path); // 将当前排列加入到结果集中
            return;
        }
 
        for (int i = 0; i < nums.size(); i++) { // 遍历给定数组中的元素
            // 如果同一树层nums[i-1]已经使用过，则直接跳过
            if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
 
            if (!used[i]) { // 当前元素未被使用
                used[i] = true; // 将该元素标记为已使用
                path.push_back(nums[i]); // 将该元素加入到当前排列中
                backtracking(nums, used); // 递归调用，继续构造剩余部分的排列
                path.pop_back(); // 回溯操作，将当前元素移出当前排列
                used[i] = false; // 将该元素标记为未使用，以便生成其他排列
            }
        }
    }
 
public:
    /**
     * 生成给定数组的全排列（包含重复元素）
     * @param nums 给定数组
     * @return 所有可能的排列结果
     */
    vectorint>> permuteUnique(vector<int>& nums) {
        result.clear(); // 清空结果数组
        path.clear(); // 清空当前排列
 
        sort(nums.begin(), nums.end()); // 对数组进行排序，使相同元素相邻
 
        vector<bool> used(nums.size(), false); // 初始化标记数组，所有元素都未被使用
 
        backtracking(nums, used); // 调用回溯函数进行排列生成
 
        return result; // 返回所有可能的排列结果
    }
};

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。