Permutations II

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].

和permutations 基本一致，只是需要先把array 排序，然后保证在同一次循环中选取的数字不同即可。

 1 public class Solution {
 2     ArrayList<ArrayList<Integer>> result = null;
 3     int len = 0;
 4     public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
 5         // Start typing your Java solution below
 6         // DO NOT write main() function
 7         Arrays.sort(num);
 8         result = new ArrayList<ArrayList<Integer>>();
 9         if(num == null || num.length == 0) return result;
10         len = num.length;
11         boolean[] item = new boolean[len];
12         get(item, num, new ArrayList<Integer>());
13         return result;
14     }
15     public void get(boolean[] item, int[] num, ArrayList<Integer> row){
16         if(row.size() == len){
17             result.add(new ArrayList<Integer>(row));
18             return;
19         }
20         for(int i = 0; i < len; i ++){
21             if(!item[i]){
22                 item[i] = true;
23                 row.add(num[i]);
24                 get(item, num, row);
25                 item[i] = false;
26                 row.remove(row.size() - 1);
27                 while(i + 1 < num.length && num[i + 1] == num[i])  
28                     i ++;
29             }
30         }
31     }
32 }

第三遍：不使用额外的boolean 数组：

 1 public class Solution {
 2     public List<List<Integer>> permuteUnique(int[] num) {
 3         ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
 4         Arrays.sort(num);
 5         getPermutation(num, num.length, new ArrayList<Integer>(), result);
 6         return result;
 7     }
 8     public void getPermutation(int[] num, int len, ArrayList<Integer> row, ArrayList<List<Integer>> result){
 9         if(num == null || len == 0){
10             result.add(row);
11             return;
12         }
13         int pre = Integer.MAX_VALUE;
14         for(int i = 0; i < num.length; i ++){
15             if(num[i] != Integer.MAX_VALUE && num[i] != pre){
16                 pre = num[i];
17                 num[i] = Integer.MAX_VALUE;
18                 ArrayList<Integer> nrow = new ArrayList<Integer>(row);
19                 nrow.add(pre);
20                 getPermutation(num, len - 1, nrow, result);
21                 num[i] = pre;
22             }
23         }
24     }
25 }

第四遍：

 1 public class Solution {
 2     ArrayList<List<Integer>> result;
 3     public List<List<Integer>> permuteUnique(int[] num) {
 4         result = new ArrayList<List<Integer>>();
 5         if(num == null || num.length == 0) return result;
 6         Arrays.sort(num);
 7         findPermutation(num, new ArrayList<Integer>());
 8         return result;
 9     }
10     
11     private void findPermutation(int[] num, ArrayList<Integer> row){
12         if(row.size() == num.length){
13             result.add(row);
14         }
15         int pre = Integer.MIN_VALUE;
16         for(int i = 0; i < num.length; i ++){
17             if(num[i] != Integer.MIN_VALUE && num[i] != pre){
18                 pre = num[i];
19                 row.add(num[i]);
20                 num[i] = Integer.MIN_VALUE;
21                 findPermutation(num, new ArrayList<Integer>(row));
22                 num[i] = pre;
23                 row.remove(row.size() - 1);
24             }
25         }
26     }
27 }