题目描述
输入一组数字（可能包含重复数字），输出其所有的排列方式。
数据范围
输入数组长度 [0,6]。
样例
输入：[1,2,3] 输出： [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
方法一：dfs O(n)
这道题存在相同的元素，所以和普通的全排列题目不同：
- 先将数组进性排序，把相同元素排在一起。
- 从左到右依次枚举每个数，每次把它放在空位上。
- 我们定义一个状态，遇到相同元素后就直接跳到下一个不同元素的位置继续枚举。
- 每次递归前后都要对状态进行更新和还原。
class Solution { public: vector<vector<int>> ans; vector<int> path; vector<bool> st; void dfs(vector<int>nums, int u, int start) { //如果已经凑满一组，则将其加入答案数组中 if (u == nums.size()) { ans.push_back(path); return; } //遍历每一个元素 for (int i = start; i < nums.size(); i++) { //如果当前元素没有在当前路径，则加入当前路径 if (!st[i]) { st[i] = true; //更新状态数组 path[i] = nums[u]; //加入当前路径 if (u + 1 < nums.size() && nums[u + 1] != nums[u]) dfs(nums, u + 1, 0); //如果相邻元素不相同，则继续遍历 else dfs(nums, u + 1, i + 1); //如果相邻元素相同，则要找到与其不同的那个元素再继续加入路径 st[i] = false; //还原状态数组 } } } vector<vector<int>> permutation(vector<int>& nums) { sort(nums.begin(), nums.end()); //先进行排序，整合相同元素 st = vector<bool>(nums.size(), false); //状态数组 path = vector<int>(nums.size()); //存储当前路径 dfs(nums, 0, 0); return ans; } };
欢迎大家在评论区交流~
