一、题目描述
给定一个不含重复数字的数组 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中的所有整数 互不相同
二、思路讲解
我们先不考虑算法，只结合实际生活中，我们要找出一串数组的全排列时，应该怎么做？以[1,2,3]为例，应该是先选出数组的1放在开头，然后再选出第二位数……
如果将每次选择的结果放在列表中，就会有以下的树形结构：
2.1 广度优先遍历
我们可以将这样的树形结构保存下来，然后按照广度优先遍历，找出最下面的叶子节点即可。
2.2 深度优先遍历
更好的方法是我们在构建这个结构的过程中就将叶子节点保存下来。
class Solution { public int []nums; public List<List<Integer>> lists = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { this.nums = nums; //用一个boolean数组标记节点是否被访问过 dfs(0, new boolean[nums.length], new ArrayList<>()); return lists; } void dfs(int count, boolean []used, List<Integer> list) { //如果list的长度达到最大 if(count == nums.length) { lists.add(new ArrayList(list)); return; } for(int i=0; i<nums.length; i++) { if(!used[i]) { list.add(nums[i]); used[i] = true; dfs(count+1, used, list); list.remove(list.size()-1); used[i] = false; } } } }
