47. Permutations II

Problem:

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:
5/28/2018
Since each for loop the valid number might not start from index 0, if the nums[i - 1] has been used(the upper level), and nums[i] == nums[i -1], we can use nums[i].
-------------------------------------------------------------------------------------------------------------------------
1/23/2018
The numbers on the same level are not used, cuz the used mark will be removed after backtracking. So the used[i - 1] checks whether nums[i - 1] has been used at upper level.
Solution:

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

--------------------------------------------------------------------------------------------------------------------------

思路：
如何去重复的问题。和combination 很像。方法很巧妙，用一个visited[]数组来记录是否被访问过。如果nums[i] == nums[i-1]，num[i-1]被访问过了则可以用nums[i]（nums[i-1]在上一层），否则就跳过。