全排列问题（LeetCode 46 47）
1 全排列问题
本篇文章主要介绍了全排列问题以及详细的解法。
给定一个数组求出其中的全排列。
其中的数组，可能带重复元素，也可能不带重复元素。
有详细思路以及递归树图解，语言包括C++、Java和Go。
下面先来看看简单的版本，不带重复元素的。
2 不带重复元素的全排列
题目链接。
2.1 思路
首先全排列是所有元素都需要选择的，也就是每次选择的时候，需要遍历一次数组中的所有元素。
考虑下样例中的[1,2,3]，如果第一次选择了[1]，那么下一次只能选择[2,3]之中的其中一个。继续，如果第二次选择了[2]，那么只剩下[3]可以选择了。也就是说，每次选择的时候，都会将候选元素的个数减少一个。
具体的选择过程以及结果如下：
同理，如果第一次选择[2]，图示如下：
如果第一次选择[3]，图示如下：
完整递归树：
3.2 代码
回到代码实现上，需要一种方式去判断上一次选择了哪些，用于在本次选择的时候，去判断不选择上一次选择的元素。在C++中，可以考虑使用unordered_set<int>。
class Solution {
private:
public:
vector<vector<int> > permute(vector<int> &nums) {
vector<vector<int> > res;
// 长度
int n = static_cast<int>(nums.size());
// 存储当前选择的元素
vector<int> cur;
// 递归函数定义，只有一个selected_index参数，表示上一次选择的下标集合
auto dfs = [&](this auto &&dfs, unordered_set<int> selected_index) -> void {
// 如果当前选择的元素列表长度为n，表明找到了一个结果，存储并返回
if (cur.size() == n) {
res.push_back(cur);
return;
}
// 枚举数组中的每个元素，也就是上面递归树中的按照水平视角来看的过程
// 在第一层中，枚举选择的[1,2,3]
// 第二层中，能选择上一层没有选择的元素
// 第三层类似，能选择第二层没有选择的元素
for (int i = 0; i < n; ++i) {
// 如果上一次选择过，跳过
// 注意这里的实现使用了下标，直接使用元素也是可以的，这里为了方便代码编写使用了下标
if (selected_index.contains(i)) {
continue;
}
// 选择了这个下标
selected_index.insert(i);
// 存储结果
cur.push_back(nums[i]);
// 选择下一层
dfs(selected_index);
// 回溯处理
cur.pop_back();
selected_index.erase(i);
}
};
// 递归入口，一开始没有选择任何元素，传入一个空集合
dfs({});
return res;
}
};
耗时14ms：
由于这里的下标范围不大，可以考虑使用位运算来优化。下标范围只有1 <= n <= 6，可以直接使用一个int来存储选择的下标。另一方面，原来的实现中每次递归的时候都会复制一次unordered_set，所以改用了位运算实现能节省了unordered_set占用的空间，以及复制所需要的时间。
class Solution {
private:
public:
vector<vector<int> > permute(vector<int> &nums) {
vector<vector<int> > res;
int n = static_cast<int>(nums.size());
vector<int> cur;
auto dfs = [&](this auto &&dfs, int selected_index) -> void {
if (cur.size() == n) {
res.push_back(cur);
return;
}
for (int i = 0; i < n; ++i) {
// 已经选择过
if (selected_index & (1<<i)){
continue;
}
// 存储该下标
selected_index |= (1<<i);
cur.push_back(nums[i]);
dfs(selected_index);
cur.pop_back();
// 回溯
selected_index &= ~(1<<i);
}
};
dfs({});
return res;
}
};
耗时：
3 带重复元素的全排列
如果元素重复会怎么样呢？
题目链接。
如果元素重复，按照上面的算法，输入[1,2,2]，就会输出：
1 2 2
1 2 2
2 1 2
2 2 1
2 1 2
2 2 1
这明显是不合题意的。
3.1 思路
为什么上面的算法会有问题呢？因为选择了重复的元素。
对于[1,2,2]来说，下面这样选择就重复了：
因此，需要跳过重复的2，具体来说，在同一层中，选择过的元素不能重复选择：
同样道理，如果第一层选择2：
这样第一层的第二个2就不能选择了，完整递归树如下：
3.2 代码实现
代码实现上和之前的类似，添加一个判断，判断同一层不选择之前选择过的元素即可。
class Solution {
private:
public:
vector<vector<int> > permuteUnique(vector<int> &nums) {
vector<vector<int> > res;
int n = static_cast<int>(nums.size());
vector<int> cur;
auto dfs = [&](this auto &&dfs, int selected_index) -> void {
if (cur.size() == n) {
res.push_back(cur);
return;
}
// 使用unordered_set保存已经选择过的值
// 注意这里不能用下标了，因为需要保存的是值
unordered_set<int> selected_digit;
for (int i = 0; i < n; ++i) {
if (selected_index & (1 << i)) {
continue;
}
// 如果包含当前已经选择过的，跳过
if (selected_digit.contains(nums[i])) {
continue;
}
selected_index |= (1 << i);
// 保存当前已经选择过的
selected_digit.insert(nums[i]);
cur.push_back(nums[i]);
dfs(selected_index);
cur.pop_back();
selected_index &= ~(1 << i);
// 回溯的时候不需要对selected_digit处理
// 因为需要保存所有已经选择过的
}
};
dfs({});
return res;
}
};
同理，在该题的范围下也能用位运算优化：
class Solution {
private:
public:
vector<vector<int> > permuteUnique(vector<int> &nums) {
vector<vector<int> > res;
int n = static_cast<int>(nums.size());
vector<int> cur;
auto dfs = [&](this auto &&dfs, int selected_index) -> void {
if (cur.size() == n) {
res.push_back(cur);
return;
}
int selected_digit = 0;
for (int i = 0; i < n; ++i) {
if (selected_index & (1 << i)) {
continue;
}
// 如果包含当前已经选择过的，跳过
// 注意值的范围是带负数的
if (selected_digit & (1<<(nums[i] + 10))){
continue;
}
selected_index |= (1 << i);
selected_digit |= (1 << (nums[i]+10));
cur.push_back(nums[i]);
dfs(selected_index);
cur.pop_back();
selected_index &= ~(1 << i);
}
};
dfs({});
return res;
}
};
4 其他语言版本——Java
4.1 不带重复元素
import java.util.*;
public class Solution {
private final List<List<Integer>> res = new ArrayList<>();
private final LinkedList<Integer> cur = new LinkedList<>();
private int[] nums;
private int n;
private void dfs(int selectedIndex) {
if (cur.size() == n) {
res.add(new ArrayList<>(cur));
return;
}
for (int i = 0; i < n; i++) {
if ((selectedIndex & (1 << i)) != 0) {
continue;
}
selectedIndex |= (1 << i);
cur.addLast(nums[i]);
dfs(selectedIndex);
cur.pollLast();
selectedIndex &= ~(1 << i);
}
}
public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
this.n = nums.length;
dfs(0);
return res;
}
}
4.2 带重复元素
import java.util.*;
public class Solution {
private final List<List<Integer>> res = new ArrayList<>();
private final LinkedList<Integer> cur = new LinkedList<>();
private int[] nums;
private int n;
private void dfs(int selectedIndex) {
if (cur.size() == n) {
res.add(new ArrayList<>(cur));
return;
}
int selectedDigit = 0;
for (int i = 0; i < n; i++) {
if ((selectedIndex & (1 << i)) != 0) {
continue;
}
if ((selectedDigit & (1 << (nums[i] + 10))) != 0) {
continue;
}
selectedIndex |= (1 << i);
selectedDigit |= (1 << (nums[i] + 10));
cur.addLast(nums[i]);
dfs(selectedIndex);
cur.pollLast();
selectedIndex &= ~(1 << i);
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
this.nums = nums;
this.n = nums.length;
dfs(0);
return res;
}
}
5 其他语言版本——Go
5.1 不带重复元素
func permute(nums []int) [][]int {
n, res, cur := len(nums), make([][]int, 0), make([]int, 0)
var dfs func(int)
dfs = func(selectedIndex int) {
if len(cur) == n {
curCopy := make([]int, len(cur))
copy(curCopy, cur)
res = append(res, curCopy)
return
}
for i := 0; i < n; i++ {
if (selectedIndex & (1 << i)) != 0 {
continue
}
selectedIndex |= (1 << i)
cur = append(cur, nums[i])
dfs(selectedIndex)
cur = cur[:len(cur)-1]
selectedIndex &= ^(1 << i)
}
}
dfs(0)
return res
}
5.2 带重复元素
func permuteUnique(nums []int) [][]int {
n, res, cur := len(nums), make([][]int, 0), make([]int, 0)
var dfs func(int)
dfs = func(selectedIndex int) {
if len(cur) == n {
curCopy := make([]int, len(cur))
copy(curCopy, cur)
res = append(res, curCopy)
return
}
selectedDigit := 0
for i := 0; i < n; i++ {
if (selectedIndex & (1 << i)) != 0 {
continue
}
if (selectedDigit & (1 << (nums[i] + 10))) != 0 {
continue
}
selectedIndex |= (1 << i)
selectedDigit |= (1 << (nums[i] + 10))
cur = append(cur, nums[i])
dfs(selectedIndex)
cur = cur[:len(cur)-1]
selectedIndex &= ^(1 << i)
}
}
dfs(0)
return res
}
6 附录
- 姐妹篇：子集问题