力扣90——子集 II

原题

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]

输出:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

原题url：https://leetcode-cn.com/problems/subsets-ii/

解题

递归

这道题，针对已经刷了不少题目的我们而言，应该第一想到的就是递归了，从第1个数开始，每次遍历1个数，如果和之前的数相同则跳过，然后以下一个数为起点，继续遍历。让我们来看看代码：

class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        // 从小到大排序

        Arrays.sort(nums);

        // 最终结果

        List<List<Integer>> result = new LinkedList<>();

        result.add(new LinkedList<>());

        // 回溯

        dfs(0, nums, new Stack<>(), result);

        return result;

    }

    public void dfs(int index, int[] nums, Stack<Integer> stack, List<List<Integer>> result) {

        if (index >= nums.length) {

            return;

        }

        for (int i = index; i < nums.length; i++) {

            // 在这一次总的查找中，如果当前节点和上一个节点相同，则跳过

            if (i > index && nums[i] == nums[i - 1]) {

                continue;

            }

            // 添加该数

            stack.push(nums[i]);

            // 作为一种情况，放进结果中

            result.add(new LinkedList<>(stack));

            // 继续回溯

            dfs(i + 1, nums, stack, result);

            // 回退

            stack.pop();

        }

    }

}

提交OK，执行用时：2 ms，内存消耗：36.5 MB，但执行用时只战胜40.16%，那就来优化一下。

优化

看了第一眼，我真的不知道该如何优化。我先是想到将递归改成迭代，但感觉并没有从时间上做出优化，不过还是给大家看一下：

class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        if (nums == null || nums.length == 0) {

            return new LinkedList<>();

        }

        // 从小到大排序

        Arrays.sort(nums);

        // 最终结果

        List<List<Integer>> result = new ArrayList<>(1 << nums.length);

        result.add(0, new LinkedList<>());

        // 上一步新解的开始下标

        int newStartIndex = 1;

        // 遍历添加

        for (int i = 0; i < nums.length; i++) {

            int j = 0;

            // 和上一个数字相同，则只针对上一步的新解增加

            if (i > 0 && nums[i] == nums[i - 1]) {

                j = newStartIndex;

            }

            int length = result.size();

            newStartIndex = length;

            for (;j < length; j++) {

                List<Integer> tempList = result.get(j);

                List<Integer> newList = new LinkedList<>(tempList);

                newList.add(nums[i]);

                result.add(newList);

            }

        }

        return result;

    }

}

提交之后，果然不出所料，和之前一样，那就再让我们想想。

还记得在之前文章中曾经说过，new LinkedList<>(Collection<? extends E> c)其内部依旧是遍历，很耗性能。因此我专门看了一下new ArrayList<>(Collection<? extends E> c)，其内部最终会调用Systemp.arraycopy。让我们再试一次：

class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        // 从小到大排序

        Arrays.sort(nums);

        // 最终结果

        List<List<Integer>> result = new LinkedList<>();

        result.add(new ArrayList<>());

        // 回溯

        dfs(0, nums, new Stack<>(), result);

        return result;

    }

    public void dfs(int index, int[] nums, Stack<Integer> stack, List<List<Integer>> result) {

        if (index >= nums.length) {

            return;

        }

        for (int i = index; i < nums.length; i++) {

            // 在这一次总的查找中，如果当前节点和上一个节点相同，则跳过

            if (i > index && nums[i] == nums[i - 1]) {

                continue;

            }

            // 添加该数

            stack.push(nums[i]);

            // 作为一种情况，放进结果中

            result.add(new ArrayList<>(stack));

            // 继续回溯

            dfs(i + 1, nums, stack, result);

            // 回退

            stack.pop();

        }

    }

}

提交之后，果然OK了，执行用时：1 ms，战胜100%的 java 提交记录。

我这里再说明一下，LinkedList 的遍历拷贝，每个元素都需要重新计算内存位置，而 ArrayList 的拷贝，可以直接一次性申请一大片空间，写入和遍历的速度会更快。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题目只要利用递归就可以解决了，但优化的时候，需要注意数据结构（是不是我之前用一些的 LinkedList 换成 ArrayList 会效果更好呢）。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

https://death00.github.io/

公众号：健程之道

力扣90——子集 II的相关教程结束。