46. Permutations
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] ]分析：
用的DFS。
注意：
1、传的是引用变量，每次递归对同一个数组进行操作，递归的返回值为空。
2、ans为引用变量，不能直接将ans加入结果集。
代码：
public class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); List<Integer> ans = new ArrayList<Integer>(); boolean visited[] = new boolean[nums.length]; if(nums.length == 0 || nums == null) return ret; for(int i = 0 ; i < nums.length ; i++) visited[i] = false; DFS(ret,nums,visited,ans); return ret; } private void DFS(List<List<Integer>> ret , int[] nums , boolean[] visited , List<Integer> ans){ if( ans.size() == nums.length ){ List<Integer> tmp = new ArrayList<Integer>(ans); ret.add(tmp); } for(int i = 0 ; i < nums.length ; i++){ if(visited[i]) continue; visited[i] = true; ans.add(nums[i]); DFS(ret,nums,visited,ans); visited[i] = false; ans.remove(ans.size()-1); } } } 25 / 25 test cases passed. Status: