LeetCode permutations

给定一个没有重复数字的序列,返回其所有可能的全排列。 > 示例: > > 输入: [1,2,3] > 输出: > [ > [1,2,3], > [1,3,2], > [2,1,3], > [2,3,1], > [3,1,2], > [3,2,1] > ]

解答:

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
36
37
38
39
40
class Solution {
public:
vector<vector<int>> permute1(vector<int>& nums) {
vector<vector<int>> res;
dfs(nums, res, 0);
return res;
}

void dfs1(vector<int> &nums, vector<vector<int>> &res, int i) {
if (i == nums.size())
res.push_back(nums);
for (int j = i; j < nums.size(); j++) {
swap(nums[i], nums[j]);
dfs1(nums, res, i+1);
swap(nums[i], nums[j]);
}
}

vector<vector<int>> permute2(vector<int>& nums) {
vector<vector<int>> res;
vector<int> tmp;
vector<bool> used(nums.size(), false);
dfs2(nums, res, 0, tmp, used);
return res;
}

void dfs2(vector<int> &nums, vector<vector<int>> &res, int i, vector<int> &tmp, vector<bool> used) {
if (i == nums.size())
res.push_back(tmp);
for (int j = 0; j < nums.size(); j++) {
if (!used[j]) {
used[j] = true;
tmp.push_back(nums[j]);
dfs2(nums, res, i+1, tmp, used);
used[j] = false;
tmp.pop_back();
}
}
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×