Version: Next

46.全排列

46. 全排列

难度 中等

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

DFS

按 DFS 套路来即可

  • 在枚举每层所有的选择时，注意本题中，元素是不可重复的，也就是之前被选过的数字，之后的层就不能再选了

如何实现不重复

  • 方法一：设置一个 boolean 数组，与元素数目一致，标识对应元素有没有使用过
    • 但是：在回溯时，必须恢复现场，因为选择元素发生了退回，则 boolean 数组的值也要同步退回
方法一 使用布尔数组
public class _46全排列 {
public List<List<Integer>> permute(int[] nums) {
Integer[] singleResult = new Integer[nums.length];
List<List<Integer>> resultList = new ArrayList<>();
boolean[] isNumUsed = new boolean[nums.length];
if (nums.length == 1) {
resultList.add(Collections.singletonList(nums[0]));
return resultList;
}
dfs(0, nums, resultList, singleResult, isNumUsed);
return resultList;
}
private void dfs(int depth, int[] nums, List<List<Integer>> resultList, Integer[] singleResult, boolean[] isNumUsed) {
if (depth == nums.length) {
// 找到了一个解，添加到结果集
resultList.add(new ArrayList<>(Arrays.asList(singleResult)));
return;
}
// 枚举当前层所有的选择
for (int i = 0; i < nums.length; i++) {
if (isNumUsed[i]) continue;
singleResult[depth] = nums[i];
isNumUsed[i] = true;
dfs(depth + 1, nums, resultList, singleResult, isNumUsed);
isNumUsed[i] = false; // 回溯回复现场
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
_46全排列 obj = new _46全排列();
List<List<Integer>> permute = obj.permute(nums);
for (List<Integer> integers : permute) {
for (Integer integer : integers)
System.out.print(integer + ", ");
System.out.print("\n");
}
}
}
  • 方法二：使用集合类 contains 过滤
使用集合简化
public List<List<Integer>> permute(int[] nums) {
List<Integer> singleResult = new ArrayList<>();
List<List<Integer>> resultList = new ArrayList<>();
if (nums.length == 1) {
resultList.add(Collections.singletonList(nums[0]));
return resultList;
}
dfs(0, nums, resultList, singleResult);
return resultList;
}
private void dfs(int depth, int[] nums, List<List<Integer>> resultList, List<Integer> singleResult) {
if (depth == nums.length) {
// 找到了一个解，添加到结果集
resultList.add(new ArrayList<>(singleResult));
return;
}
// 枚举当前层所有的选择
for (int num : nums) {
if (singleResult.contains(num)) continue;
singleResult.add(num);
dfs(depth + 1, nums, resultList, singleResult);
singleResult.remove(singleResult.size() - 1); // 回溯回复现场
}
}
  • 但是，contains 方法使得时间复杂度变高

DFS 最佳实现

对于输入 [1, 2, 3]

  • 在第 0 层，让 下标0 分别与 下标 0、1、2 交换
  • 在第 1 层，让下标1 分别与 下标 1、2 交换
  • .. 以此类推
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> resultList = new ArrayList<>();
if (nums.length == 1) {
resultList.add(Collections.singletonList(nums[0]));
return resultList;
}
dfs(0, nums, resultList);
return resultList;
}
private void dfs(int depth, int[] nums, List<List<Integer>> resultList) {
if (depth == nums.length) {
// 找到了一个解，添加到结果集
List<Integer> singleResList = new ArrayList<>();
for (int n : nums)
singleResList.add(n);
resultList.add(singleResList);
return;
}
// 枚举当前层所有的选择
// 从当前层 对应数值的下标开始遍历 ， 因为之前的位置已经选定了
for (int i = depth; i < nums.length; i++) {
swap(nums, depth, i);
dfs(depth + 1, nums, resultList);
swap(nums, depth, i); // 回溯 恢复现场
}
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}