leetcode90. 子集 II(java)

这篇具有很好参考价值的文章主要介绍了leetcode90. 子集 II(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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 子集 。和子集问题区别就是,这里有重复值的问题,我们要进行剪枝。
示例:
leetcode90. 子集 II(java)
要对重复的值,进行剪枝操作,反应到代码里,就是我们先把数组排序,使其相等的数字相邻,然后回溯时,已经选过的,直接跳过去。

代码演示

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. 组合

leetcode40. 组合总和 II文章来源地址https://www.toymoban.com/news/detail-494554.html

到了这里,关于leetcode90. 子集 II(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 90.子集II

    原题链接:90.子集II 思路: 重点就是去重 也就是同层的去重操作 全代码:

    2024年02月04日
    浏览(33)
  • 力扣每日一题90:子集

    给你一个整数数组  nums  ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。 解集  不能  包含重复的子集。返回的解集中,子集可以按  任意顺序  排列。 示例 1: 示例 2: 提示: 1 = nums.length = 10 -10 = nums[i] = 10 通过次数 330.7K 提交次数 520.9K 通过率 63

    2024年02月06日
    浏览(30)
  • 代码随想录23| 93.复原IP地址, 78.子集, 90.子集II

    题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址

    2024年02月11日
    浏览(90)
  • 代码随想录刷题笔记 DAY 28 | 复原 IP 地址 No.93 | 子集 No.78 | 子集 II No.90

    01. 复原 IP 地址(No. 93) 题目链接 代码随想录题解 1.1 题目 有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0 ),整数之间用 \\\'.\\\' 分隔。 例如: \\\"0.1.2.201\\\" 和 \\\"192.168.1.1\\\" 是 有效 IP 地址,但是 \\\"0.011.255.245\\\" 、 \\\"192.168.1.312\\\" 和 \\\"192.168@1.1\\\" 是 无效 I

    2024年02月22日
    浏览(50)
  • 力扣:416. 分割等和子集 & 1049. 最后一块石头的重量 II (动态规划)(二合一,一次吃透两道题)

    力扣:416. 分割等和子集 1049. 最后一块石头的重量 II 用的方法都是01背包解法,思路也是近乎一样,这里就放在一起讲解了(主要讲解第一题,第二题大家可以直接自己AC)。01背包解法详细讲解请见上篇博客01背包问题(二) 给你一个 只包含正整数 的 非空 数组 nums 。请你判断

    2024年01月20日
    浏览(50)
  • [Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    内容:今天复习下dp数组中的背包问题 分割等和子集 - 能否装满 最后一块石头 - 尽可能装满 目标和 - 有多少种方法装 一和零 - 装满背包有多少个物品 416. 分割等和子集 10背包:用/不用;有容量;有价值 dp[j] : 容量为j,最大价值为dp[j]         重量和价值等价 dp[target] == t

    2024年02月16日
    浏览(42)
  • 40. 组合总和 II - 力扣(LeetCode)

    题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 输入示例 输出示例 解题代码

    2024年01月23日
    浏览(40)
  • leetcode(力扣) 2866. 美丽塔 II

    原题链接 每次选取下标 i 为峰值, 进行 n 次,对每次取max就可以找到答案 对于 i 左边的序列: 需要满足序列是非递减的, 同时每个值尽可能大 所以满足: j 的位置上的数 = (j, i] 上的最小的值 (等于时取得最大值) , 同时需要保证 j 位置上的数要小于heights[j] (题目中的要求,美丽

    2024年04月29日
    浏览(37)
  • 力扣(LeetCode)算法_C++——存在重复元素 II

    存在重复元素 II 给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) = k 。如果存在,返回 true ;否则,返回 false 。 示例 1: 输入:nums = [1,2,3,1], k = 3 输出:true 示例 2: 输入:nums = [1,0,1,1], k = 1 输出:true 示例

    2024年02月09日
    浏览(36)
  • leetcode416. 分割等和子集(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/partition-equal-subset-sum 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。

    2024年02月11日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包