[LintCode] 16 Permutations II 解题报告

Description
Given a list of numbers with duplicate number in it. Find all unique permutations.


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

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

Challenge
Using recursion to do it is acceptable. If you can do it without recursion, that would be great!


思路
还是是套模版。
和Permutation这题不同的是这题需要考虑重复的问题。我们可以参考Subset II去重的思路。
还是先排序。以[1, 2¹, 2², 2³]为例，上标表示重复的这个数字出现的先后。
在把候选数字放入list的时候，我们不允许候选数字已经在list里，也不允许例如2³在2²还没有有选之前就选择。
判断的方法是维护一个visit的数组来表示某一个元素有没有已经在list里了。



Code

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            result.add(list);
            return result;
        }
        
        Arrays.sort(nums);
        
        boolean[] visit = new boolean[nums.length];
        search(nums, list, result, visit);
        return result;
    } 
    
    public void search( int[] nums, 
                        List<Integer> list, 
                        List<List<Integer>> result, 
                        boolean[] visit) {
        
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }                    
        
        for (int i = 0; i < nums.length; i++) {
            if (visit[i] || (i != 0 && !visit[i - 1] && nums[i] == nums[i - 1])) {
                continue;
            }
            visit[i] = true;
            list.add(nums[i]);
            search(nums, list, result, visit);
            list.remove(list.size() - 1);
            visit[i] = false;
        }
        
        return;
    }
}