前言：
目前你们对“算法中的全排列”都比较着重，朋友们都想要剖析一些“算法中的全排列”的相关资讯。那么小编也在网上搜集了一些有关“算法中的全排列””的相关文章，希望大家能喜欢，你们快快来了解一下吧！大厂高频算法面试题：《全排列问题系列》，您将学到如何设计递归，递归的好坏直接影响到动态规划，其次递归涉及到深度优先遍历时，要考虑恢复现场，如何剪枝，如何去重等技巧。
一、全排列问题 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 case ArrayList<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;}三、总结增加去重表（剪枝）：去重标记，在递归发生的过程中去重，剪掉
不剪枝（过滤）：不增加去重表，递归全部跑完，收集的结果中去重（Set）
递归函数的设计好坏直接影响到动态规划递归涉及到深度优先遍历时，要考虑恢复现场递归过程中是否走过，可以增加标记表，剪枝效果递归完毕后，也可以增加Set表去重，过滤效果
作者：mzoe666888
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #算法中的全排列
