|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -importcom.fishercoder.common.utils.CommonUtils; |
4 | | - |
5 | 3 | importjava.util.ArrayList; |
6 | 4 | importjava.util.Arrays; |
7 | 5 | importjava.util.List; |
8 | 6 |
|
9 | | -/**Given a collection of numbers that might contain duplicates, return all possible unique permutations. |
| 7 | +/** |
| 8 | + * 47. Permutations II |
| 9 | + * |
| 10 | + * Given a collection of numbers that might contain duplicates, return all possible unique permutations. |
10 | 11 |
|
11 | 12 | For example, |
12 | 13 | [1,1,2] have the following unique permutations: |
|
16 | 17 | [2,1,1] |
17 | 18 | ]*/ |
18 | 19 | publicclass_47 { |
19 | | -/**credit: https://discuss.leetcode.com/topic/31445/really-easy-java-solution-much-easier-than-the-solutions-with-very-high-vote*/ |
20 | | -publicList<List<Integer>>permuteUnique(int[]nums) { |
21 | | -List<List<Integer>>result =newArrayList(); |
22 | | -if (nums ==null ||nums.length ==0) { |
| 20 | +publicstaticclassSolution1 { |
| 21 | +/** |
| 22 | + * credit: https://discuss.leetcode.com/topic/31445/really-easy-java-solution-much-easier-than-the-solutions-with-very-high-vote |
| 23 | + */ |
| 24 | +publicList<List<Integer>>permuteUnique(int[]nums) { |
| 25 | +List<List<Integer>>result =newArrayList(); |
| 26 | +if (nums ==null ||nums.length ==0) { |
| 27 | +returnresult; |
| 28 | + } |
| 29 | +boolean[]used =newboolean[nums.length]; |
| 30 | +List<Integer>list =newArrayList(); |
| 31 | +Arrays.sort(nums); |
| 32 | +dfs(nums,used,list,result); |
23 | 33 | returnresult; |
24 | 34 | } |
25 | | -boolean[]used =newboolean[nums.length]; |
26 | | -List<Integer>list =newArrayList(); |
27 | | -Arrays.sort(nums); |
28 | | -dfs(nums,used,list,result); |
29 | | -returnresult; |
30 | | - } |
31 | 35 |
|
32 | 36 |
|
33 | | -privatevoiddfs(int[]nums,boolean[]used,List<Integer>list,List<List<Integer>>result) { |
34 | | -if (list.size() ==nums.length) { |
35 | | -result.add(newArrayList(list)); |
36 | | -return; |
37 | | - } |
38 | | -for (inti =0;i <nums.length;i++) { |
39 | | -if (used[i]) { |
40 | | -continue; |
| 37 | +privatevoiddfs(int[]nums,boolean[]used,List<Integer>list,List<List<Integer>>result) { |
| 38 | +if (list.size() ==nums.length) { |
| 39 | +result.add(newArrayList(list)); |
| 40 | +return; |
41 | 41 | } |
42 | | -if (i >0 &&nums[i -1] ==nums[i] && !used[i -1]) { |
43 | | -continue; |
| 42 | +for (inti =0;i <nums.length;i++) { |
| 43 | +if (used[i]) { |
| 44 | +continue; |
| 45 | + } |
| 46 | +if (i >0 &&nums[i -1] ==nums[i] && !used[i -1]) { |
| 47 | +continue; |
| 48 | + } |
| 49 | +/** |
| 50 | + * For this line, both !used[i-1] and used[i-1] will AC. It is because the first one makes sure when |
| 51 | + * duplicates are selected, the order is ascending (index from small to large). However, |
| 52 | + * the second one means the descending order. |
| 53 | + */ |
| 54 | +used[i] =true; |
| 55 | +list.add(nums[i]); |
| 56 | +dfs(nums,used,list,result); |
| 57 | +used[i] =false; |
| 58 | +list.remove(list.size() -1); |
44 | 59 | } |
45 | | -/** |
46 | | - * For this line, both !used[i-1] and used[i-1] will AC. It is because the first one makes sure when |
47 | | - * duplicates are selected, the order is ascending (index from small to large). However, |
48 | | - * the second one means the descending order. |
49 | | - */ |
50 | | -used[i] =true; |
51 | | -list.add(nums[i]); |
52 | | -dfs(nums,used,list,result); |
53 | | -used[i] =false; |
54 | | -list.remove(list.size() -1); |
55 | 60 | } |
56 | 61 | } |
57 | | - |
58 | | -publicstaticvoidmain(String...args) { |
59 | | -int[]nums =newint[]{1,1,2}; |
60 | | -_47test =new_47(); |
61 | | -List<List<Integer>>result =test.permuteUnique(nums); |
62 | | -CommonUtils.printListList(result); |
63 | | - } |
64 | 62 | } |