47. Permutations II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

Code

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(num);
        helper(res, nums, new ArrayList<>(), new HashSet<>());
        return res;
    }

    private void helper(List<List<Integer>> res,
                        int[] nums,
                        List<Integer> temp,
                        HashSet<Integer> visited){

        if(temp.size() == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            // 两步去重的方法
            // 防止重复使用自己
            if(visited.contains(i)) continue;
            // 防止重复使用同样的数字
            if(i > 0 && nums[i] == nums[i - 1] && !visited.contains(i - 1)) continue;
            temp.add(nums[i]);
            visited.add(i);
            helper(res, nums, temp, visited);
            temp.remove(temp.size() - 1);
            visited.remove(i);
        }
    }
}