这两题都是用回溯算法解决问题的。
题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
| 输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
|
本题主要参考labuladong的算法小抄里的解法，总体思路不难，代码如下。主要改动在于第17行，labuladong的解法里用于判断当前元素是否已经加入当前路径的时候，是直接在当前路径数组里查找是否存在该元素的，用C++代码写起来是if (std::find(track.begin(), track.end(), nums[i]) != track.end())，这样的写法应对第46题是没问题的，因为题目已经说了给的序列中没有重复数字。改动后维护了一个visitedbool数组，初始化全部元素未为false，用于记录给定序列中的每个元素是否已经加入当前路径了，与之对应的代码是第21行和第24行，用于改变元素出入路径时的visited数组维护。这个改动是为了第47题做准备的。
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
| class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> track;
vector<bool> visited(nums.size(), false);
backtrack(nums, track, res, visited);
return res;
}
void backtrack(vector<int>& nums, vector<int>& track, vector<vector<int>>& res, vector<bool>& visited) {
if (track.size() == nums.size()) {
res.push_back(track);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (visited[i]) {
continue;
}
track.push_back(nums[i]);
visited[i] = true;
backtrack(nums, track, res, visited);
track.pop_back();
visited[i] = false;
}
}
};
|
题目描述：给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
示例：
1
2
3
4
5
6
7
8
| 输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
此题与46题的主要区别在于减去了输入序列元素不可重复的限制，但输出的全排列不得重复，因此在回溯过程中需要有剪枝操作。这一题的思路参考了leetcode题解的解答思路，主要是画了一个下面的图，就比较容易理解了：
- 在图中 ② 处，搜索的数也和上一次一样，但是上一次的
1 还在使用中；
- 在图中 ① 处，搜索的数也和上一次一样，但是上一次的
1 刚刚被撤销，正是因为刚被撤销，下面的搜索中还会使用到，因此会产生重复，剪掉的就应该是这样的分支
解决这个题目画图的话，重点是维护这个visited数组（或者图中的used数组），这样就比较容易找到其中的规律。回溯的返回条件仍然是路径的长度等于输入序列的长度，判断循环何时该跳过时，一种是与46题一样碰到已经加入路径的元素（代码第18-19行），另一种是应该剪枝的情况（代码第21-23行），注意在一开始就将输入序列做了排序，这样可以把重复元素聚集在一起。剪枝条件是当前元素是重复元素（即nums[i] == nums[i-1]）并且前面与之重复的元素未被使用（即visited[i-1] == 0），即图中的①处。
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
| class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
vector<vector<int>> res;
vector<int> track;
vector<bool> visited(nums.size(), false);
backtrack(nums, track, res, visited);
return res;
}
void backtrack(vector<int>& nums, vector<int>& track, vector<vector<int>>& res, vector<bool>& visited) {
if (track.size() == nums.size()) {
res.push_back(track);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (visited[i]) {
continue;
}
if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) {
continue;
}
track.push_back(nums[i]);
visited[i] = true;
backtrack(nums, track, res, visited);
track.pop_back();
visited[i] = false;
}
}
};
|