全排列问题系列，您将学到如何设计递归，递归的好坏直接影响到动态规划，其次递归涉及到深度优先遍历时，要考虑恢复现场，如何剪枝，如何去重等技巧。
给定一个不含重复数字的数组 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> permute(int[] nums) {
list> ans = new arraylist<>();
hashset rest = new hashset<>();
for (int num : nums) {
rest.add(num);
}
arraylist path = new arraylist<>();
f(rest, path, ans);
return ans;
}
// rest中有剩余数字，已经选过的数字不在rest中，选过的数字在path里
public static void f(hashset rest, arraylist path, list> ans) {
if (rest.isempty()) {
ans.add(path);
} else {
for (int num : rest) {
arraylist curpath = new arraylist<>(path);
curpath.add(num);
hashset clone = cloneexceptnum(rest, num);
f(clone, curpath, ans);
}
}
}
public static hashset cloneexceptnum(hashset rest, int num) {
hashset clone = new hashset<>(rest);
clone.remove(num);
return clone;
}
2.2、方法二
public static list> permute(int[] nums) {
list> 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> ans) {
if (index == nums.length) { // base case
arraylist 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;
}
给定一个可包含重复数字的序列 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> permuteunique(int[] nums) {
list> ans = new arraylist<>();
process(nums, 0, ans);
return ans;
}
public static void process(int[] nums, int index, list> ans) {
if (index == nums.length) {
arraylist cur = new arraylist<>();
for (int num : nums) {
cur.add(num);
}
ans.add(cur);
} else {
hashset 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表去重，过滤效果