含有重复元素的全排列

剑指 Offer II 084. 含有重复元素集合的全排列

难度中等4

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

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

注意：本题与主站 47 题相同： https://leetcode-cn.com/problems/permutations-ii/

回溯去重

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        backtrack(nums,0);
        return ans;
    }

    List<List<Integer>> ans = new ArrayList<>();
    public void backtrack(int []nums,int index){
        int n = nums.length;
        if(index==n-1){
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<n;i++){
                list.add(nums[i]);
            }
            ans.add(list);
            return;
        }
        // 通过set去重，如果某个数字与index处的数字交换过一次，那么下次不用再次交换（不然就出现重复了）
        Set<Integer> set =  new HashSet<>(); 
        for(int i = index; i < n; i++){
            if(set.contains(nums[i]))continue;
            set.add(nums[i]);
            swap(nums,index,i);
            backtrack(nums,index+1);
            swap(nums,index,i);
        }
    }

    public void swap(int []nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

赏

谢谢你请我吃糖果

微信