题目描述

题解

回溯算法

本题与第一道子集问题(78题)的唯一区别在于存在重复元素, 因为不确定数组是否是有序的, 所以需要先将数组排序

排序后的数组重复元素在一起, 才能方便处理

做这道题需要明确的一点是: 重复的元素只影响到了同级的选择

例如对于数组1, 2, 2, 遍历到第一个元素2时, 可以添加两个路径: 2和2, 2, 因为这是由同一个起点出发的

但是第二个2作为起点就不行了, 因为上一个起点与它是同级的, 只会产生相同的路径

代码并不复杂, 只是多了几句判断元素重复性的语句

public class lc90 {
    List<List<Integer>> res;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        int len = nums.length;
        Arrays.sort(nums);
        process(nums, 0, len, path);
        return res;
    }

    private void process(int[] nums, int i, int len, List<Integer> path) {

        res.add(new ArrayList<>(path));
        for (int j = i; j < len; j++) {
            if (j>i&&nums[j]== nums[j-1]){
                continue;
            }
            path.add(nums[j]);
            process(nums, j+1, len, path);
            path.remove(path.size()-1);
        }
    }
}