给定一个可能包含重复元素的整数数组 nums, 返回该数组所有可能的子集(幂集).
说明: 解集不能包含重复的子集.
示例:
输入: [1,2,2]
输出:
- [
- [2],
- [1],
- [1,2,2],
- [2,2],
- [1,2],
- []
- ]
链接: https://leetcode-cn.com/problems/subsets-ii
基本思路: 与题目 leetcode78 子集 差不多, 由于 Java 默认的 sort 函数是从小到大的, 所以在求子集的过程中是从后往前的. 每 cur 每次减一 (增加一个新数字) 产生的新子集是将新数字添加到从 finalRes 的第 ii 到第 len 个元素的并集. 如图
新增加的数字添加到上一部分 (框框内) 组成下一轮的输出. 它有一个范围 (即框框内的) 下标为[ii,len].78 题则是新添加的数字添加到所有的 finalRes 元素中.
- /**
- *
- * @param nums: 从大到小的有序数组
- * @param n: 数组长度
- * @param cur: 当前位置
- * @param finalRes: 最终结果
- * @param i:finalRes 起始位置
- */
- private void result(int[] nums,int n, int cur, List<List<Integer>> finalRes, int i){
- if (cur == -1){
- return;
- }
- int len = finalRes.size()-1;
- int ii = (nums[cur] != nums[cur+1]) ? 1 : i;
- // 当前位置也是一个子集, 故添加
- if (nums[cur] != nums[cur+1]) {
- List<Integer> elem = new ArrayList<>();
- elem.add(nums[cur]);
- finalRes.add(elem);
- }
- for (int j = ii; j <= len; ++j){
- List<Integer> e = new ArrayList<>();
- e.add(nums[cur]);
- e.addAll(finalRes.get(j));
- finalRes.add(e);
- }
- result(nums, n, cur-1, finalRes, len+1);
- }
- public List<List<Integer>> subsetsWithDup(int[] nums) {
- // 将数组排序
- Arrays.sort(nums);
- List<List<Integer>> res = new ArrayList<>();
- List<Integer> elem1 = new ArrayList<>();
- res.add(elem1);
- // 生成最后一个重复数字的子集
- List<Integer> elem2 = new ArrayList<>();
- elem2.add(nums[nums.length-1]);
- res.add(elem2);
- int i;
- for (i = nums.length-2; i>= 0 && nums[i] == nums[i+1]; --i){
- List<Integer> e = new ArrayList<>();
- e.add(nums[i]);
- e.addAll(res.get(res.size()-1));
- res.add(e);
- }
- result(nums, nums.length, i, res, 1);
- return res;
- }
来源: http://www.bubuko.com/infodetail-3210356.html