写点什么

【LeetCode】子集二 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 04 月 12 日

题目

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。


解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。


示例 1:


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


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/problems/subsets-ii

代码

public class DayCode {    public static void main(String[] args) {        int[] nums = new int[]{1, 2, 2};        List<List<Integer>> ans = new DayCode().subsetsWithDup(nums);        System.out.println(ans.toString());    }
List<Integer> temp = new ArrayList<>(); List<List<Integer>> ans = new ArrayList<>();
/** * 时间复杂度 O(n * 2 的 n 次方) * 空间复杂度 O(n) * @param nums * @return */ public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); dfs(false, 0, nums); return ans; }
private void dfs(boolean choosePre, int cur, int[] nums) { if (cur == nums.length) { ans.add(new ArrayList<>(temp)); return; } dfs(false, cur + 1, nums); if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) { return; } temp.add(nums[cur]); dfs(true, cur + 1, nums); temp.remove(temp.size() - 1); }}
复制代码

总结

  • 子集二是子集问题的延续,和子集问题的不同,是要处理子集的重复性。

  • 常见的处理数组重复子元素的方法是先将数组排序,然后对重复元素处理,进行跳过。在 three sum 中,我们也应用了相同的处理方法。

  • 在不断的刷题过程中,常见的数据处理方法需要熟记,可以提升我们的做题效率。

  • 坚持每日一题,加油!

发布于: 2021 年 04 月 12 日阅读数: 14
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】子集二Java题解