順列II、再帰で重複を削除する

Question

重複した番号のリストが与えられている場合。ユニークな順列をすべて見つけてください。ヘプラーと呼ばれる方法で

For numbers [1,2,2] the unique permutations are: 
[ 
    [1,2,2], 
    [2,1,2], 
    [2,2,1] 
] 

、重複を除去するために、私は、if文を持っている：

if (i != 0 && nums[i] == nums[i-1] && !set.contains(i-1)) { 
    continue; 
} 

が、私はset.contains(i-1)に!set.contains(i - 1)を変更した場合、それは（まだ正しいだことがわかりましたleetcodeが受け入れられる）、それは!set.contains(i - 1)でなければなりません。

誰もがその理由を知っていますか？

class Solution { 
/** 
* @param nums: A list of integers. 
* @return: A list of unique permutations. 
*/ 
public List<List<Integer>> permuteUnique(int[] nums) { 
    List<List<Integer>> list = new ArrayList<List<Integer>>(); 

    if (nums == null) { 
     return list; 
    } 

    if (nums.length == 0) { 
     list.add(new ArrayList<Integer>()); 
     return list; 
    } 

    Arrays.sort(nums); 

    HashSet<Integer> set = new HashSet<Integer>(); 
    ArrayList<Integer> current = new ArrayList<Integer>(); 
    helper(nums, list, current, set); 

    return list; 
} 

public void helper(int [] nums, 
        List<List<Integer>> list, 
        ArrayList<Integer> current, 
        HashSet<Integer> set){ 

    if(current.size() == nums.length) { 
     list.add(new ArrayList<Integer>(current)); 
     return; 
    } 

    for (int i = 0; i < nums.length; i++) { 

     if (set.contains(i)) { 
      continue; 
     } 

     if (i != 0 && nums[i] == nums[i-1] && !set.contains(i-1)) { 
      continue; 
     } 

     current.add(nums[i]); 
     set.add(i); 
     helper(nums, list, current, set); 
     set.remove(i); 
     current.remove(current.size() - 1); 
    } 
    } 
} 

Answer 1

Wikiページには、繰り返し要素でうまく機能するpermutation algorithm to get the next lexicographic permutationが記載されています。擬似コード：

Initialisation: 
    Start with sorted combination - here [1,2,2] 

Next permutation step: 

    Find the largest index k such that a[k] < a[k + 1]. If no such index exists, 
    the permutation is the last permutation. 

    Find the largest index l greater than k such that a[k] < a[l]. 

    Swap the value of a[k] with that of a[l]. 

    Reverse the sequence from a[k + 1] up to and including the final element a[n].