一、题目
1、算法题目
“给定一个整数数组，返回该数组所有可能的子集，解集不能包含重复的元素。”
题目链接：
来源：力扣（LeetCode）
链接：90. 子集 II - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1： 输入： nums = [1,2,2] 输出： [[],[1],[1,2],[1,2,2],[2],[2,2]] 复制代码
示例 2： 输入： nums = [0] 输出： [[],[0]] 复制代码
二、解题
1、思路分析
本题根据78题【子集】改进而来，可以先再复习一下78题解法，再来看这道题。
对于这道题来说，可以使用迭代进行子集的枚举，但是需要避免重复的子集。
对于当前数组来说，如果当前选择的数x有与其相同的数y，并且没有选择y，那么此时包含x的子集，必然会出现包含y的所有子集中。
对于上述起那个框，可以先将数组排序，然后判断当前数组与上一个数相同，就可以跳过当前生成的子集，就可以避免重复子集。
2、代码实现
代码参考：
class Solution { List<Integer> t = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); int n = nums.length; for (int mask = 0; mask < (1 << n); ++mask) { t.clear(); boolean flag = true; for (int i = 0; i < n; ++i) { if ((mask & (1 << i)) != 0) { if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) { flag = false; break; } t.add(nums[i]); } } if (flag) { ans.add(new ArrayList<Integer>(t)); } } return ans; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n x 2n)
其中n是数组的长度，排序时间复杂度为O(n log n)，一共有2n个状态，每个状态需要O(n)的时间来构造，所以是 O(n x 2n)。
空间复杂度： O(n)
其中n是数组的长度，只需要使用一个临时数组n的空间即可。
三、总结
对于子集的问题，使用回溯算法是一种很好的方法。
回溯算法是深度优先遍历算法，对于子集问题，排列问题而言，不计较一个组合内元素的顺序性。
