题目
给你一个整数数组 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 中，我们也应用了相同的处理方法。
在不断的刷题过程中，常见的数据处理方法需要熟记，可以提升我们的做题效率。
坚持每日一题，加油！
评论