Permutations II

1. 记得排序

2. 记得维护一个used 数组

3. 记得查重 i > 0 && nums[i-1] == nums[i] && !used[i-1]

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]
]

注意重复数的情况

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

Permutations II 和Permutations o(n!)