77 * Description:
88 *
99 * Given a collection of numbers that might contain duplicates, return all
10- * possible uniquepermutations .
10+ * possible uniquesubs .
1111 *
1212 * For example,
13- * [1,1,2] have the following uniquepermutations :
13+ * [1,1,2] have the following uniquesubs :
1414 * [1,1,2], [1,2,1], and [2,1,1].
1515 *
1616 ***************************************************************************
17- * {@link https://leetcode.com/problems/permutations -ii/ }
17+ * {@link https://leetcode.com/problems/subs -ii/ }
1818 * P.S.: cannot skip duplicates using while (nums[i] == duplicate) because
1919 * after swapping, duplicates may be separated (one duplicate is swapped with
2020 * and goes to somewhere else disconnected with other duplicates)
@@ -37,44 +37,44 @@ public List<List<Integer>> permuteUnique(int[] nums) {
3737 }
3838Arrays .sort (nums );
3939int index =0 ;
40- List <Integer >permutation =new ArrayList <Integer >();
41- permuteUnique (nums ,index ,permutation ,result );
40+ List <Integer >sub =new ArrayList <Integer >();
41+ permuteUnique (nums ,index ,sub ,result );
4242return result ;
4343 }
4444
45- private void permuteUnique (int []nums ,int index ,
46- List <Integer >permutation ,List <List <Integer >>result ) {
47-
45+ private void permuteUnique (int []nums ,int index ,List <Integer >sub ,
46+ List <List <Integer >>result ) {
4847// base case
4948if (index ==nums .length ) {
50- // one validpermutation found
51- result .add (permutation );
49+ // one validsub found
50+ result .add (sub );
5251return ;
5352 }
5453
5554// recursive case
5655// either use set or sort nums[index]:nums[end] to avoid duplicates
5756Set <Integer >appearred =new HashSet <Integer >();
5857for (int i =index ;i <nums .length ;i ++) {
59- // try each number among nums[index],...,nums[end]
60- // as permutation[index], remember to skip duplicates!
61- if (appearred .contains (nums [i ]) ==false ) {
62- // swap nums[i] with nums[index]
63- swap (nums ,i ,index );
58+ if (appearred .contains (nums [i ])) {
59+ // duplicates appear
60+ continue ;
61+ }
62+ appearred .add (nums [i ]);
63+ // swap nums[i] with nums[index]
64+ swap (nums ,i ,index );
6465
65- // go on searching
66- List <Integer >copy =new ArrayList <Integer >(permutation );
67- copy .add (nums [index ]);
68- permuteUnique (nums ,index +1 ,copy ,result );
66+ // go on searching
67+ List <Integer >copy =new ArrayList <Integer >(sub );
68+ copy .add (nums [index ]);
69+ permuteUnique (nums ,index +1 ,copy ,result );
6970
70- // swap back nums[i] with nums[index]
71- swap (nums ,index ,i );
71+ // swap back nums[i] with nums[index]
72+ swap (nums ,index ,i );
7273
73- appearred .add (nums [i ]);
74- }
7574 }
7675 }
7776
77+ // swap two numbers in an array
7878private void swap (int []nums ,int i ,int index ) {
7979if (i <nums .length &&index <nums .length ) {
8080int temp =nums [i ];