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 := 0for 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 附录

• 姐妹篇：子集问题