给定一个可包含重复字母的序列,按任意顺序返回所有不重复的全排 列。
时间: 2024-05-01 15:16:39 浏览: 22
思路:回溯法
1. 对序列进行排序,方便去重和回溯。
2. 回溯过程中,维护一个used数组,记录每个元素是否被使用过。
3. 在每一层回溯中,遍历未使用过的元素,并将其加入path中,递归到下一层。
4. 当path长度等于序列长度时,说明已经找到一个全排列,将其加入结果集中。
5. 在回溯过程中,如果发现当前元素和前一个元素相同且前一个元素未被使用过,则可以直接跳过当前元素,避免重复。
时间复杂度:O(n*n!),其中n为序列长度。因为有n!种可能的全排列,每种全排列需要O(n)的时间复杂度来判断是否重复。
代码实现:
```
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 排序,方便回溯和去重
backtrack(nums, used, path, res);
return res;
}
void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
if (path.size() == nums.size()) { // 找到一个全排列
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue; // 去重
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, used, path, res);
used[i] = false;
path.pop_back();
}
}
};
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)