47. Permutations II

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

For example,
[1,1,2] have the following unique permutations:

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

一刷
题解：
求全排列，但元素可能有重复。去重复就成为了关键。dfs+回溯，比如1134，最外层就是求出第一个元素，比如 1， 2， 3， 里面的嵌套dfs再负责第二，三，四个元素。 我们使用了一个数组 - boolean[] visited。这个数组用来在dfs过程中记录已经访问过的值来避免计算重复。同时我们在dfs和backtracking的时候也要回溯这个数组。 经过上述步骤，我们就可以避免在dfs的时候有重复了。比如输入数组为[1, 1, 1]， 则这个最后的结果 {[1, 1, 1]}是在最外层被加入到res中去的。 我们也要注意在遍历数组的时候，假如 visited[i]或者(i > 0 && nums[i] == nums[i - 1] && visited[i - 1])，要continue。
这样可以保证{1(1), 1(2), 1(3)}只会以{1(3), 1(2), 1(1)}的形式出现

Time Complexity - O(n!)， Space Complexity - O(n)

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        permuteUnique(res, new ArrayList<Integer>(), visited, nums);
        return res;
    }
    
    private void permuteUnique(List<List<Integer>> res, List<Integer>onePerm, 
    boolean[] visited, int[] nums){
        if(onePerm.size() == nums.length){
            res.add(new ArrayList<>(onePerm));
            return;
        }
        
        for(int i=0; i<nums.length; i++){
            if(visited[i] || ((i>0) && nums[i] == nums[i-1] && visited[i-1]))
                continue;
            visited[i] = true;
            onePerm.add(nums[i]);
            permuteUnique(res, onePerm, visited, nums);
            onePerm.remove(onePerm.size()-1);
            visited[i] = false;
        }
    }
}

二刷
注意条件：if(visited[i] || ((i>0) && nums[i] == nums[i-1] && visited[i-1])) continue;
保证例如[1(1)1(2) 1(3) 2]只会出现[1(3),1(2),1(1)这种组合出现

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        permute(nums, res, new ArrayList<>(), visited);
        return res;
    }
    
    private void permute(int[] nums, List<List<Integer>> res, List<Integer> list,
                        boolean[] visited){
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=0; i<nums.length; i++){
            if(visited[i] || (i>0) && nums[i] == nums[i-1] && visited[i-1]) continue;
            list.add(nums[i]);
            visited[i] = true;
            permute(nums, res, list, visited);
            visited[i] = false;
            list.remove(list.size()-1);
        }
    }
}