内卷大厂系列《全排列问题二连击》

作者：mzoe666888

大厂高频算法面试题：《全排列问题系列》，您将学到如何设计递归，递归的好坏直接影响到动态规划，其次递归涉及到深度优先遍历时，要考虑恢复现场，如何剪枝，如何去重等技巧。

一、全排列问题 I

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

leetcode

1、分析

方法一：暴力解，当前来到i位置，i之前的位置（左边）已经做了选择，只能从i开始向右边做选择，从N个数中选一个，然后i+1位置上从N-1个数中选一个，i+2位置从N-2个数中选一个

arr[0...i]已经做了选择，从arr[i+1...]做选择

方法二：深度优先遍历，当前来到index位置，arr[0...index-1]位置上的数已经选好了，从arr[index...N-1]选数，把每轮收集的排列用ans收集起来，记得要清理现场，深度优先遍历一概的技巧。

2、实现

2.1、方法一

public static List<List<Integer>> permute(int[] nums) {List<List<Integer>> ans = new ArrayList<>();HashSet<Integer> rest = new HashSet<>();for (int num : nums) {rest.add(num);}ArrayList<Integer> path = new ArrayList<>();f(rest, path, ans);return ans;
}// rest中有剩余数字，已经选过的数字不在rest中，选过的数字在path里
public static void f(HashSet<Integer> rest, ArrayList<Integer> path, List<List<Integer>> ans) {if (rest.isEmpty()) {ans.add(path);} else {for (int num : rest) {ArrayList<Integer> curPath = new ArrayList<>(path);curPath.add(num);HashSet<Integer> clone = cloneExceptNum(rest, num);f(clone, curPath, ans);}}
}public static HashSet<Integer> cloneExceptNum(HashSet<Integer> rest, int num) {HashSet<Integer> clone = new HashSet<>(rest);clone.remove(num);return clone;
}

2.2、方法二

public static List<List<Integer>> permute(int[] nums) {List<List<Integer>> ans = new ArrayList<>();process(nums, 0, ans);return ans;
}// 当前来到 index 位置，之前的nums[0...index-1] 的数已经选好了，从num[index...]开始选数
// 选好的答案放在ans里
public static void process(int[] nums, int index, List<List<Integer>> ans) {if (index == nums.length) { // base caseArrayList<Integer> cur = new ArrayList<>();for (int num : nums) {cur.add(num);}ans.add(cur);} else {for (int j = index; j < nums.length; j++) {swap(nums, index, j);process(nums, index + 1, ans);swap(nums, index, j); // 深度优先遍历，清理现场}}
}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;
}

二、全排列问题 II

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

leetcode

1、分析

全排列问题II就是在全排列问题I的基础上增加去重机制，仅此而已。

2、实现

public static List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> ans = new ArrayList<>();process(nums, 0, ans);return ans;
}public static void process(int[] nums, int index, List<List<Integer>> ans) {if (index == nums.length) {ArrayList<Integer> cur = new ArrayList<>();for (int num : nums) {cur.add(num);}ans.add(cur);} else {HashSet<Integer> set = new HashSet<>();  // 防重for (int j = index; j < nums.length; j++) {if (!set.contains(nums[j])) {set.add(nums[j]);swap(nums, index, j);process(nums, index + 1, ans);swap(nums, index, j);}}}
}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;
}