打印数组的全部排列
作者：Grey
原文地址：
无重复值情况
题目描述见: LeetCode 46. Permutations
主要思路
由于是所有排列，所以每个 i 后面位置的元素都有机会来到 i 位置。
定义递归函数
void p(int[] arr, int i, List<List<Integer>> result)
递归含义是：数组 arr 的 i 位置以后的元素，都来到 i 位置（即：和 i 位置的元素交换），得到的排列是多少。
所以，base case 是，当 i 来到 arr 的最后一个元素的位置的时候，此时可以收集一种排列状况（因为最后一个元素后面没有元素可以与之交换了）
if (i == arr.length - 1) {
// 来到最后一个位置，收集答案
result.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
return;
}
到普遍位置的时候，即遍历 i 后面的每个位置，让每个位置都和 i 位置的值交换
for (int j = i; j < arr.length; j++) {
swap(arr, i, j);
p(arr, i + 1, result);
swap(arr, i, j);
}
完整代码见
class Solution {
public static List<List<Integer>> permute(int[] arr) {
if (arr == null ) {
return Collections.emptyList();
}
if (arr.length == 0) {
List<List<Integer>> ans = new ArrayList<>();
ans.add(new ArrayList<>());
return ans;
}
List<List<Integer>> result = new LinkedList<>();
p(arr, 0, result);
return result;
}
private static void p(int[] arr, int i, List<List<Integer>> result) {
if (i == arr.length - 1) {
// 来到最后一个位置，收集答案
result.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
return;
}
for (int j = i; j < arr.length; j++) {
swap(arr, i, j);
p(arr, i + 1, result);
swap(arr, i, j);
}
}
public static void swap(int[] arr, int i, int j) {
if (i != j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
}
有重复值情况
题目描述见: LeetCode 47. Permutations II
有重复值的情况可以借鉴上述递归方法的思想，我们还是定义如下递归函数
void p(int i, int[] arr, List<List<Integer>> result)
递归含义还是：数组 arr 的 i 位置以后的元素，都来到 i 位置（即：和 i 位置的元素交换），得到的排列是多少。
但是由于有重复值，所以我们在交换之前，需要判断和 i 交换的元素曾经有没有访问过，如下示意图
当我们将i位置的 a 和 i + n位置的 x 交换过以后，得到了一个全排列的数量，当我们来到i+n+1位置的时候，如果这个位置还是 x ，就无须再和 i 位置的 a 交换了。
为了标识哪个值是否交换过，我们可以定义一个boolean类型的数组，由于题目中的数据范围比较小-10<=num[i]<=10, 所以我们只需要一个boolean[] visited = new boolean[21]长度的数组即可。要判断某个位置的值 m 是否访问过，只需要判断visited[m+10]是否为 TRUE。
完整代码见
class Solution {
public static List<List<Integer>> permuteUnique(int[] arr) {
List<List<Integer>> ans = new ArrayList<>();
p(0, arr, ans);
return ans;
}
private static void p(int i, int[] arr, List<List<Integer>> result) {
if (i == arr.length - 1) {
// 来到最后一个位置，收集答案
result.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
return;
}
boolean[] visited = new boolean[21];
for (int index = i; index < arr.length; index++) {
if (!visited[arr[index] + 10]) {
visited[arr[index] + 10] = true;
swap(index, i, arr);
p(i + 1, arr, result);
swap(index, i, arr);
}
}
}
private static void swap(int i, int j, int[] arr) {
if (j == i) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}