[Java恶补day51] 46. 全排列

给定一个不含重复数字的数组 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] <= 10
nums 中的所有整数 互不相同

知识点：
回溯、数组

解：
核心思路：
用数组记录节点是否被访问过
用集合记录已访问的节点
每次遍历时，选择一个未被访问的节点进行访问
恢复现场的目的：假设当前遍历节点3，但结果不满足，需要回溯到上一个节点，若不恢复现场，节点3将不能再访问了

时间复杂度：$O(n\ast n!)$。从根节点到叶子节点的路径长度之和，共有n!个节点
空间复杂度：$O(n)$。

class Solution {public List<List<Integer>> permute(int[] nums) {//获取数组大小int len = nums.length;//存储结果List<List<Integer>> res = new ArrayList<>();//路径List<Integer> path = Arrays.asList(new Integer[len]); // 所有排列的长度都是len//是否遍历过boolean[] isUsed = new boolean[len];//执行DFSdfs(0, nums, len, res, path, isUsed);return res;}private void dfs(int depth, int[] nums, int len, List<List<Integer>> res, List<Integer> path, boolean[] isUsed) {//叶子节点if (depth == len) {res.add(new ArrayList<>(path));return;}//遍历所有节点for (int i = 0; i < len; i++) {//未访问过if (!isUsed[i]) {//从未选过的数字中选一个path.set(depth, nums[i]);//标记为已访问isUsed[i] = true;//递归下一个节点dfs(depth + 1, nums, len, res, path, isUsed);//恢复现场isUsed[i] = false;//路径无需恢复现场，因为排列长度固定，直接覆盖即可}}}
}

参考：
1、灵神题解