给定一个不含重复数字的数组?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]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums?中的所有整数?互不相同
????????回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。
方法：回溯
? ? ? ? 问题等价：有 n 个排列成一行的空格，需要从左往右依此填入给定的 n 个数，每个数只能使用一次。——> 穷举法，从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，可以用「回溯法」来模拟这个过程。
定义递归函数 backtrack(first, output) 表示从左往右填到第 first 个位置，当前排列为 output。 那么整个递归函数分为两个情况：
- 如果 first==n，说明我们已经填完了 n?个位置（注意下标从 0 开始），找到了一个可行的解，将 output 放入答案数组中，递归结束。
- 如果 first<n，要考虑这第 first 个位置要填哪个数。根据题目要求不能填已经填过的数，因此很容易想到的一个处理手段是定义一个标记数组 visited[] 来标记已经填过的数，那么在填第 first 个数的时候遍历题目给定的 n 个数，如果这个数没有被标记过，就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first + 1, output)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。
????????使用标记数组来处理填过的数是一个很直观的思路，但是可不可以去掉这个标记数组来降低空间复杂度呢？
????????思路：将题目给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，在回溯的时候只要动态维护这个数组即可。
- 假设已经填到第 first 个位置，那么nums 数组中 [0,first?1] 是已填过的数的集合，[first,n?1] 是待填的数的集合。
- 尝试用[first,n?1] 里的数去填第 first 个数，假设待填的数的下标为 i?，那么填完以后将第 i?个数和第 first 个数交换，即能使得在填第 first+1个数的时候 nums 数组的 [0,first] 部分为已填过的数，[first+1,n?1] 为待填的数，回溯的时候交换回来即能完成撤销操作。
????????举例：假设有 [2, 5, 8, 9, 10] 这 5 个数要填入，已经填到第 3 个位置，已经填了 [8,9] 两个数，那么这个数组目前为 [8, 9 | 2, 5, 10] 这样的状态，分隔符区分了左右两个部分。假设这个位置要填 10 这个数，为了维护数组，将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8, 9, 10 | 2, 5] 。
????????这样生成的全排列并不是按字典序存储在答案数组中的，如果题目要求按字典序输出，则用标记数组或者其他方法。
下面的图展示了回溯的整个过程：
方法一：交换进行每个位置数字的选择，不能保证字典序
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> perm = new ArrayList<>();
for(int num : nums){
perm.add(num);
}
int len = nums.length;
backtrace(len, perm, res, 0);
return res;
}
public void backtrace(int len, List<Integer> perm, List<List<Integer>> res, int first){
// 判断结束条件
if(first == len){
res.add(new ArrayList<Integer>(perm));
return;
}
for(int i = first; i < len; i ++){
// 动态维护数组
Collections.swap(perm, first, i);
// 递归进行下一个数的选择
backtrace(len, perm, res, first + 1);
// 撤销操作
Collections.swap(perm, first, i);
}
}
}方法二：先排序使得按照字典序输出
class Solution {
public static List<List<Integer>> permute(int[] nums) {
// 回溯法+递归
// 声明返回值的存储空间
List<List<Integer>> lists = new ArrayList<>();
// 判断数组中元素的个数
if(nums.length == 0) {
return lists;
}
// 声明空间
ArrayList<Integer> al = new ArrayList<>();
// 排序
Arrays.sort(nums);
// 回溯遍历
depthFirstSearch(lists, al, nums);
return lists;
}
public static void depthFirstSearch(List<List<Integer>> lists, ArrayList<Integer> al, int[] nums) {
// 判断数组元素，到达叶子节点，将路径装入结果列表
if (nums.length == al.size()) {
lists.add(new ArrayList<>(al));
return;
} else {
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择，不能重复
if(al.contains(nums[i])) {
continue;
}
// 做选择
al.add(nums[i]);
// 递归调用，进入下一层
depthFirstSearch(lists, al, nums);
// 状态重置，撤销当前选择
al.remove(al.size() - 1);
}
}
}
}方法三：访问数组标记
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> perm = new ArrayList<>();
if(nums.length == 0){
return res;
}
boolean[] used = new boolean[nums.length];
backtrace(perm, res, used, nums, 0);
return res;
}
public void backtrace(List<Integer> perm, List<List<Integer>> res, boolean[] used, int[] nums, int depth){
// 判断结束条件
if(depth == nums.length){
res.add(new ArrayList<Integer>(perm));
return;
}
// 对每个元素进行判断，如果没有使用则进入回溯
for (int i = 0; i < used.length; i++) {
if (!used[i]) {
perm.add(nums[i]);
used[i] = true;
backtrace(perm, res, used, nums, depth + 1);
perm.remove(perm.size() - 1);
used[i] = false;
}
}
}
}
「为什么在往结果集中添加排列结果的时候，需要进行new ArrayList添加」
????????假设这段代码，「正确」res.add(new ArrayList<>(output)); 变为「错误」res.add(output); 关键在于res存放的是list引用。 那么回溯过程中，将数字使用状态重置撤销的时候，会将list的元素移除掉，也会影响到res里面的list情况。因为它们是同一个引用。 全部为空，是因为回溯结束的同时，会将全部数字重置撤销，这样list里面的元素就会为空了，同样的，也会影响到res的存放情况。