题目难度： Medium
原题描述：
Given a collection of distinct numbers, return all possible permutations.
For example, [1,2,3] have the following permutations:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
题目大意：
给你若干个不相同的数，要求返回这些数的所有排列。
解题思路：
这是一道经典的求全排列的问题。一开始先标记所有的数均未被访问，在算法的主体中，我们可以设想将原数组填写到一个新的数组中，当这个新数组填满时，就得到一个排列。当填写新数组的第一个位置时，有n种可能的数填写，第二个位置有n-1种可能，一直到最后一个位置，只有一种可能，这样一共有n!种排列。这个思想可以用dfs实现，在dfs中，每一个填写的位置用for循环遍历每一个可能填写的数，填写过的数要标记为已访问，待当层递归结束后再标记为未访问。
时间复杂度分析：
由于总的排列数是n！，n为一个排列里数的个数，因此总的时间复杂度为O(n！)。
以下是代码：
public class Solution { private static List<List<Integer>> ans = new ArrayList< List<Integer> >(); private void dfs(int[] nums , int cur , Integer[] p , boolean[] vis) { if(cur >= nums.length){ ans.add( new ArrayList<Integer>(Arrays.asList(p)) ); return; } for(int i=0 ; i<nums.length ; ++i){ if(!vis[i]){ vis[i] = true; p[cur] = nums[i]; dfs(nums, cur+1, p, vis); vis[i] = false; } } } public List<List<Integer>> permute(int[] nums) { ans.clear(); Integer[] p = new Integer[nums.length]; boolean[] vis = new boolean[nums.length]; for(int i=0 ; i<vis.length ; ++i){ vis[i] = false; } dfs(nums, 0, p, vis); return ans; } }
