题目要求：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
核心逻辑
选一个数 -> 标记已用-> 递归-> 撤销选择（回溯)-> 继续选
1. path:当前排列的路径
比如[1,2]正在拼，下一步加3->[1,2,3]
2. used[]：标记数字是否用过
避免同一个数字在一个排列里出现两次
3. 回溯：撤销选择
path.remove(最后一个)
used[i] = false
回去换另一个数字继续尝试
一句话总结
全排列 = 回溯 + 标记 used + 路径 path
这是所有回溯题的模板！
完整代码实现如下：
import java.util.*;
class Solution {
// 存放最终结果
List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {// 记录当前路径List<Integer> path = new ArrayList<>();// 标记数字是否用过boolean[] used = new boolean[nums.length];backtrack(nums, path, used);return res;
}// 回溯核心方法
private void backtrack(int[] nums, List<Integer> path, boolean[] used) {// 出口：路径长度 == 数组长度 → 找到一个排列if (path.size() == nums.length) {res.add(new ArrayList<>(path)); // 必须 new！return;}// 遍历所有选择for (int i = 0; i < nums.length; i++) {// 用过的跳过if (used[i]) continue;// 选择used[i] = true;path.add(nums[i]);// 递归backtrack(nums, path, used);// 撤销选择（回溯）path.remove(path.size() - 1);used[i] = false;}
}
}
代码解释
1. 为什么要 new ArrayList<>(path)？
因为path是同一个List对象，从头到尾都在变：
加元素、删元素、再加、再删
你 res.add(path) 只是把这个对象的引用存进去了。到最后回溯全部结束时，path又变回空了，
所以你存进去的所有引用，指向的都是最后那个空list
2. new ArrayList<>(path) 到底干了啥？
它是拷贝一份当前的path，生成一个新对象，创建了一个副本，这样下次对path修改时，并不会改变副本的内容
3. 整个递归回溯的过程解释：
假设数组为[1,2,3]
首先for遍历到1，把1标记为true后加入到path数组中，之后递归查找1开头的所有排列，第一层递归for循环遍历到2，把2标记为true后加入到path，之后再进入第二层递归，for循环遍历到3，将3标记为ture后加入到path中，之后进入第三层递归，此时path.size()==nums.length。将新建一个数组对象，并赋值path。new ArrayList<>(path)并加入到结果数组res中。执行return,退出返回到第二层递归，执行回溯，将3移除path，并且标记为false。再返回第一层递归，将2移除，标记为false。在当前层的递归继续执行for循环，for遍历到3，将3加入path并标记为true，再执行递归，for遍历到2后将2加入path并标记，再执行递归，将path加入到res中，返回上层递归，将2删除并标记为false。因为这一层的递归for遍历到2，因此for需要接着遍历到3，因为3已经标记为true了，退出for循环。回到第一层递归，将3移除后标记为false。因为第一层的递归，for循环已经遍历到3了，退出循环，返回到第0层递归方法，执行回溯，将1删除并标记为false。第0层for循环继续遍历到2，将2标记为true并加入到path中，执行递归找到2开头的全排列。以此类推，找到3开头的全排列。最后path回溯删除全部元素后，for循环已经遍历到头，path最终为空数组。因此每次将path添加到res结果数组当中的时候，需要创建一个新对象，将path拷贝到其中,即：new ArrayList<>(path)