全排列II[存在相同元素去重 + 标准回溯]

前言

对于全排列问题，一般采用DFS进行枚举（标准回溯），而当数组中出现重复元素时，就会枚举出重复的集合。
如何去重，把相等的元素靠在一起（可排序），然后通过pre和cur是否相同，从而来去重。

一、全排列II

二、把元素靠在一起 + 标准回溯

package everyday.medium;

import java.util.*;

// 全排列II
public class PermuteUnique {
    
    public List<List<Integer>> permuteUnique(int[] nums) {
    
        // 先排序，让连续的数字放在相邻处，才好配合pre来去重。
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> el = new ArrayList<>();
        // Set 记录哪些数字已经被用了。
        Set<Integer> set = new HashSet<>();
        // dfs搜索方式取全排列。
        dfs(nums, el, ans, set);
        // 返回dfs后填充好的list
        return ans;
    }

    private void dfs(int[] nums, List<Integer> el, List<List<Integer>> ans, Set<Integer> set) {
    
        // 当每个元素都被选择，拿去排列了，则添加该排列到list中。
        if (el.size() == nums.length) {
    
            ans.add(new ArrayList<>(el));
            return;
        }
        // 标准回溯
        // 去重，当在该位置上选择不同的两个数，而这两个数相等时，产生重复。
        int pre = 1 << 31;
        for (int i = 0; i < nums.length; i++) {
    
            // 当前后选择的两个元素一样 | 这个元素已经被选了，则过。
            if (pre == nums[i] || set.contains(i)) continue;
            // 标准回溯
            el.add(nums[i]);
            set.add(i);
            dfs(nums, el, ans, set);
            set.remove(i);
            el.remove(el.size() - 1);
            // 更新pre为当前选择的元素，为下面的选择做准备。
            pre = nums[i];
        }
    }
}

总结

1）标准回溯
2）通过把元素靠在一起，再配合pre 和 cur 变量是否相等来达到去重的目的。

参考文献

[1] LeetCode 全排列II