leetcode90. 子集 II
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/subsets-ii
题目描述
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
解题思路
这个和子集问题是一样的,都是回溯算法标准模式。子集问题参考leetcode78 子集 。和子集问题区别就是,这里有重复值的问题,我们要进行剪枝。
示例:
要对重复的值,进行剪枝操作,反应到代码里,就是我们先把数组排序,使其相等的数字相邻,然后回溯时,已经选过的,直接跳过去。
代码演示
class Solution {
List<List<Integer>> ans = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
process(nums,0);
return ans;
}
/**
* 回溯算法
*/
public void process(int[]nums,int index){
ans.add(new LinkedList<>(track));
//选择列表,也就是决策列表
for(int i = index;i < nums.length;i++){
//剪枝操作,如果前面选择过了,就不选了 直接跳过
if(i > index && nums[i] == nums[i - 1]){
continue;
}
//选择
track.addLast(nums[i]);
process(nums,i + 1);
//撤销选择
track.removeLast();
}
}
}
回溯算法专题
leetcode78 子集
leetcode77. 组合文章来源:https://www.toymoban.com/news/detail-494554.html
leetcode40. 组合总和 II文章来源地址https://www.toymoban.com/news/detail-494554.html
到了这里,关于leetcode90. 子集 II(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!