包含重复元素的数组全排列

LeetCode 排列问题解决方案 -- 手稿_V1.017 在 LeetCode 中，手稿_V1.017 是一个经典的排列问题，要求返回所有不重复的全排列。这个问题的难点在于如何去除重复的排列。下面我们将讨论两种解决方案：使用 set 去重和排序 + 筛选回溯。 方法一：C++_不筛选回溯 + set 去重 在这个方法中，我们使用递归回溯来生成所有可能的排列，然后使用 set 来去重。下面是实现代码： ```cpp class Solution { private: void helper(set<vector<int>>& svi, vector<int>& cur, vector<int>& nums, vector<int>& visited) { if (cur.size() == nums.size()) { svi.insert(cur); return; } for (int i = 0; i < nums.size(); i++) { if (visited[i]) { continue; } else { cur.push_back(nums[i]); visited[i] = 1; helper(svi, cur, nums, visited); visited[i] = 0; cur.pop_back(); } } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> svi; vector<int> cur; vector<int> visited(nums.size(), 0); helper(svi, cur, nums, visited); return vector<vector<int>>(svi.begin(), svi.end()); } }; ``` 这个方法的时间复杂度是 O(n!),其中 n 是输入数组的长度。空间复杂度是 O(n),用于存储递归调用栈和 set。 方法二：C++_排序 + 筛选回溯 在这个方法中，我们首先对输入数组进行排序，然后使用递归回溯来生成所有可能的排列。在回溯过程中，我们使用一个布尔数组来记录每个元素是否已经被访问过。如果某个元素已经被访问过，我们就跳过它，避免重复排列。下面是实现代码： ```cpp class Solution { private: void helper(vector<vector<int>>& res, vector<int>& cur, vector<int>& nums) { if (cur.size() == nums.size()) { res.push_back(cur); return; } for (int i = 0; i < nums.size(); i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } cur.push_back(nums[i]); helper(res, cur, nums); cur.pop_back(); } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; vector<int> cur; sort(nums.begin(), nums.end()); helper(res, cur, nums); return res; } }; ``` 这个方法的时间复杂度是 O(n!),其中 n 是输入数组的长度。空间复杂度是 O(n),用于存储递归调用栈和结果数组。 这两个方法都可以解决 LeetCode 的排列问题，但是第二种方法更加高效，因为它使用排序和筛选来避免重复排列。