Given a collection of 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],
and [3,2,1].
思路有两个，一个是dfs，一个是递归。
dfs的关键是，有一个visited数组来标记哪些元素访问过。这个非常重要，因为我第一次面试就卡在了这个上。。。
1 public class Solution { 2 public static ArrayList<ArrayList<Integer>> permute(int[] num) { 3 boolean[] visited = new boolean[num.length]; 4 ArrayList<Integer> tmp = new ArrayList<Integer>(); 5 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 6 permute2(num, visited, tmp, result); 7 return result; 8 } 9 10 public static void permute2(int[] num, boolean[] visited, ArrayList<Integer> tmp, ArrayList<ArrayList<Integer>> result) { 11 if (tmp.size() == num.length) { 12 result.add(new ArrayList<Integer>(tmp)); 13 return; 14 } 15 for (int i=0; i<num.length; i++) { 16 if (visited[i] == false) { 17 tmp.add(num[i]); 18 visited[i] = true; 19 permute2(num, visited, tmp, result); 20 visited[i] = false; 21 tmp.remove(tmp.size()-1); 22 } 23 } 24 } 25 }
递归很好想，就是先产生[1,2],[2,1].然后在把3放到对应的位置上。
1 public class Solution { 2 public ArrayList<ArrayList<Integer>> permute(int[] num) { 3 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 4 if (num == null || num.length == 0) return null; 5 else if (num.length == 1) { 6 ArrayList<Integer> cell = new ArrayList<Integer>(); 7 cell.add(num[0]); 8 result.add(cell); 9 } 10 else { 11 int[] l = new int[num.length-1]; 12 int t = num[num.length-1]; 13 for (int i = 0; i<l.length; i++) l[i] = num[i]; 14 ArrayList<ArrayList<Integer>> current = permute(l); 15 for (ArrayList<Integer> c : current) { 16 int size = c.size(); 17 for (int j = 0; j<=size; j++) { 18 ArrayList<Integer> w = new ArrayList<Integer>(); 19 w.addAll(c); 20 w.add(j, t); 21 result.add(w); 22 } 23 } 24 } 25 return result; 26 } 27 }
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2] have the following unique
permutations:[1,1,2], [1,2,1],
and [2,1,1].
有重复数字的话，用递归就不是很好做。每一次产生一个结果就要判断这个结果是否已经包含在result中，所以时间长。
用dfs做的话用两个地方需要注意。
一个是要对字符串进行排序。因为如果排序的话，可以很好避免因为重复数字产生的重复的情况。
第二个就是如何避免因为重复数字产生的重复情况。因为已经排好序，所以每次选择下一个数字的时候只要避免和之前的数字重复就行。
比如[1,2,3,3,4].当我们产生[1,2,3]的时候，我们只要避免回溯的时候再次选择3，从而产生[1,2,3]就行了。
1 public class Solution { 2 public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { 3 Arrays.sort(num); 4 boolean[] visited = new boolean[num.length]; 5 ArrayList<Integer> tmp = new ArrayList<Integer>(); 6 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 7 permute2(num, visited, tmp, result); 8 return result; 9 } 10 11 public static void permute2(int[] num, boolean[] visited, ArrayList<Integer> tmp, ArrayList<ArrayList<Integer>> result) { 12 if (tmp.size() == num.length) { 13 result.add(new ArrayList<Integer>(tmp)); 14 return; 15 } 16 for (int i=0; i<num.length; i++) { 17 if (visited[i] == false) { 18 tmp.add(num[i]); 19 visited[i] = true; 20 permute2(num, visited, tmp, result); 21 visited[i] = false; 22 tmp.remove(tmp.size()-1); 23 while (i<num.length-1 && num[i] == num[i+1]) i++; 24 } 25 } 26 } 27 }