|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.Arrays; |
| 5 | +importjava.util.List; |
| 6 | + |
| 7 | +importutils.CommonUtils; |
| 8 | + |
| 9 | +publicclassPermutationsII { |
| 10 | +/**Looked at this post: https://discuss.leetcode.com/topic/31445/really-easy-java-solution-much-easier-than-the-solutions-with-very-high-vote*/ |
| 11 | +publicList<List<Integer>>permuteUnique(int[]nums) { |
| 12 | +List<List<Integer>>result =newArrayList(); |
| 13 | +if (nums ==null ||nums.length ==0)returnresult; |
| 14 | +boolean[]used =newboolean[nums.length]; |
| 15 | +List<Integer>list =newArrayList(); |
| 16 | +Arrays.sort(nums); |
| 17 | +dfs(nums,used,list,result); |
| 18 | +returnresult; |
| 19 | + } |
| 20 | + |
| 21 | + |
| 22 | +privatevoiddfs(int[]nums,boolean[]used,List<Integer>list,List<List<Integer>>result) { |
| 23 | +if (list.size() ==nums.length){ |
| 24 | +result.add(newArrayList(list)); |
| 25 | +return; |
| 26 | + } |
| 27 | +for (inti =0;i <nums.length;i++){ |
| 28 | +if (used[i])continue; |
| 29 | +if (i >0 &&nums[i -1] ==nums[i] && !used[i -1]) |
| 30 | +continue; |
| 31 | +/** |
| 32 | + * For this line, both !used[i-1] and used[i-1] will AC. It is because the first one makes sure when |
| 33 | + * duplicates are selected, the order is ascending (index from small to large). However, |
| 34 | + * the second one means the descending order. |
| 35 | + */ |
| 36 | +used[i] =true; |
| 37 | +list.add(nums[i]); |
| 38 | +dfs(nums,used,list,result); |
| 39 | +used[i] =false; |
| 40 | +list.remove(list.size()-1); |
| 41 | + } |
| 42 | + } |
| 43 | + |
| 44 | + |
| 45 | +publicstaticvoidmain(String...args){ |
| 46 | +int[]nums =newint[]{1,1,2}; |
| 47 | +PermutationsIItest =newPermutationsII(); |
| 48 | +List<List<Integer>>result =test.permuteUnique(nums); |
| 49 | +CommonUtils.printIntegerList(result); |
| 50 | + } |
| 51 | +} |