1 #include "000库函数.h"
2
3
4 //使用排序，感觉在作弊，但是题目没说不可以
5 //36ms
6 class Solution {
7 public:
8 vector<vector<int>> permuteUnique(vector<int>& nums) {
9 vector<vector<int>>res;
10 if (nums.empty())return res;
11 sort(nums.begin(), nums.end());//排序
12 do {
13 res.push_back(nums);
14 } while (next_permutation(nums.begin(), nums.end()));
15 return res;
16 }
17 };
18
19 ////使用递归
20 class Solution {
21 public:
22 vector<vector<int>> permuteUnique(vector<int>& nums) {
23 vector<vector<int>>Res;
24 if (nums.empty())return Res;
25 Combin(Res, nums, 0);//回溯
26 //set<vector<int>>s;
27 //s.insert(Res.begin(), Res.end());//去重
28 //Res.assign(s.cbegin(), s.cend());
29 return Res;
30 }
31 void Combin(vector<vector<int>>&Res, vector<int>v, int s) {
32 if (s >= v.size()) //此处不return，在for中结束后自动结束
33 Res.push_back(v);
34
35 for (int i = s; i < v.size(); ++i) {
36 if (s != i && v[i] == v[s])//去重
37 continue;
38 swap(v[s], v[i]);//交换
39 Combin(Res, v, s + 1);//回溯
40 swap(v[s], v[i]);//换回来
41
42 }
43 }
44
45 };
46 //
47 //////使用DFS递归
48 class Solution {
49 public:
50 vector<vector<int>> permuteUnique(vector<int>& num) {
51 vector<vector<int>> res;
52 vector<int> out, visited(num.size(), 0);
53 permuteDFS(num, 0, visited, out, res);
54 //set<vector<int>>s;
55 //s.insert(res.begin(), res.end());//去重
56 //res.assign(s.cbegin(), s.cend());
57 return res;
58 }
59 void permuteDFS(vector<int>& num, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
60 if (level == num.size()) { res.push_back(out); return; }//数字大小达到要求
61 for (int i = 0; i < num.size(); ++i) {
62 if (visited[i] == 1) continue;
63 visited[i] = 1;//该数据已经选用
64 out.push_back(num[i]);
65 permuteDFS(num, level + 1, visited, out, res);
66 out.pop_back();//回溯
67 visited[i] = 0;
68 }
69 }
70 };
71
72 //当n = 1时，数组中只有一个数a1，其全排列只有一种，即为a1
73 //
74 //当n = 2时，数组中此时有a1a2，其全排列有两种，a1a2和a2a1，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a1的前后两个位置分别加入了a2
75 //
76 //当n = 3时，数组中有a1a2a3，此时全排列有六种，分别为a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在a1a2和a2a1的基础上在不同的位置上加入a3而得到的。
77 //
78 //_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3
79 //
80 //_ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3
81 class Solution {
82 public:
83 vector<vector<int>> permute(vector<int>& num) {
84 vector<vector<int>> res;
85 if (num.empty()) return res;
86 int first = num[0];
87 num.erase(num.begin());//删除此数字
88 vector<vector<int>> words = permute(num);
89 for (auto &a : words) {
90 for (int i = 0; i <= a.size(); ++i) {
91 a.insert(a.begin() + i, first);
92 res.push_back(a);
93 a.erase(a.begin() + i);
94 }
95 }
96 return res;
97 }
98 };
99
100 void T047() {
101 vector<int>n;
102 Solution s;
103 n = { 1,1,2 };
104 for (auto &a : s.permuteUnique(n)) {
105 for (auto b : a)
106 cout << b << " ";
107 cout << endl;
108 }
109
110 }
