Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input:
 [1,1,2]

Output:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Analysis

这一题接Permutations，用常规模板，要注意的是duplicate的处理。有重复元素时，通常会先sort，这样处理起来比较方便，因为sort后，重复元素会具有连续的index。

LeetCode上有一个很有意思的讨论帖：https://leetcode.com/problems/permutations-ii/discuss/18594/Really-easy-Java-solution-much-easier-than-the-solutions-with-very-high-vote

就是在于当判断出现重复元素时，如何处理。帖主给出的是：

if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

但是人们发现以下同样可以work：

if(i>0 &&nums[i-1]==nums[i] && used[i-1]) continue;

其实区别就在于是出现重复元素的时候，是用第一个还是最后一个。帖主的方法更优化。

简单一点的理解就是因为在循环中，如果nums[i - 1]用过了，那么在backtracking的时候其实是会把used[i - 1]重新设成false的，used[ i - 1]为false，其实是说明nums[ i - 1]在i - 1的时候被使用过了。

另外还有一个更好的方式，直接增加一个内层循环，跑出连续的重复元素:

while (i < nums.length - 1 && nums[i + 1] == nums[i]){
                i++;
            }

Solution

Backtracking - 1

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        permuteHelper(nums, used, new LinkedList<Integer>(), ans);

        return ans;
    }

    private void permuteHelper(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new LinkedList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            path.add(nums[i]);
            used[i] = true;
            permuteHelper(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

Backtracking - 2

相比Permutations，只是在permuteHelper的for-loop里面最后增加了一段，来skip掉重复的元素

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        permuteHelper(nums, used, new LinkedList<Integer>(), ans);

        return ans;
    }

    private void permuteHelper(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new LinkedList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }

            path.add(nums[i]);
            used[i] = true;
            permuteHelper(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
            while (i < nums.length - 1 && nums[i + 1] == nums[i]){
                i++;
            }
        }
    }
}

Backtracking - Swap

https://leetcode.com/problems/permutations-ii/discuss/18648/Share-my-Java-code-with-detailed-explanantion

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return ans;
        }
        helper(ans, nums, 0);
        return ans;
    }

    private void helper(List<List<Integer>> ans, int[] nums, int start){
        if(start == nums.length){
            ans.add(convertToList(nums));
            return;
        }

        for(int i=start;i<nums.length;i++){
            if(!containsDuplicates(nums, start, i)){
                swap(nums, start, i);
                helper(ans, nums, start+1);
                swap(nums, start, i);
            }
        }
    }

    private boolean containsDuplicates(int[] nums, int start, int i){
        for(int j=start;j<i;j++){
            if(nums[j] == nums[i]){
                return true;
            }
        }
        return false;
    }

    private List<Integer> convertToList(int[] nums){
        List<Integer> item = new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++){
            item.add(nums[i]);
        }
        return item;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}