首页 > 代码库 > 47. Permutations II

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]
]
从头开始且避免同级重复元素的出现,就用visited, 如果前一个没被访问则后一个不能被访问, 因为结果容器已经存在了
if (visited[i] == 1) { continue; } if (i > 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0) { continue; } visited[i] = 1;
public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        
        if (nums.length == 0) {
            result.add(list);
            return result;
        }
        
        int[] visited = new int[nums.length] ;
        for (int i = 0; i < nums.length; i++) {
            visited[i] = 0;
        }
        Arrays.sort(nums);
        helper(result, list, nums, visited);
        return result;
        
    } 
    private void helper(List<List<Integer>> result,  List<Integer> list,
                        int[] nums, int[] visited) {
        if (list.size() == nums.length ) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 1)  {           
                continue;
            }
            if (i > 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0) {
                continue;
            }
            visited[i] = 1;
            list.add(nums[i]);                  
            helper(result, list, nums, visited);
             
            visited[i] = 0;
            list.remove(list.size() - 1); 
        }
    }

  

47. Permutations II