题目：
全排列回溯：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <vector>
#include <unordered_set>
using std::vector;
using std::unordered_set;
class Solution {
private:
void backtrace(vector<vector<int> > &res, vector<int> &track, unordered_set<int> &tset, vector<int> &nums)
{
if (track.size() == nums.size()) {
res.push_back(track);
}
for (int num : nums) {
if (!tset.count(num)) {
track.push_back(num);
tset.insert(num);
backtrace(res, track, tset, nums);
track.pop_back();
tset.erase(num);
}
}
}
public:
vector<vector<int> > permute(vector<int> &nums)
{
vector<vector<int> > res;
vector<int> track;
unordered_set<int> tset;
backtrace(res, track, tset, nums);
return res;
}
};
|
另一种写法，使用 swap 把值交换到当前位置，恢复就再交换一次。这种速度最快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <vector>
using std::vector;
class Solution {
private:
void backtrace(vector<vector<int> > &res, vector<int> &nums, int pos)
{
int n = nums.size();
if (pos == n) {
res.push_back(nums);
return;
}
for (int i = pos; i < n; i++) {
std::swap(nums[i], nums[pos]);
backtrace(res, nums, pos + 1);
std::swap(nums[i], nums[pos]);
}
}
public:
vector<vector<int> > permute(vector<int> &nums)
{
vector<vector<int> > res;
backtrace(res, nums, 0);
return res;
}
};
|
