文档章节

求数组的子集(含重复)Subsets II

叶枫啦啦
 叶枫啦啦
发布于 2017/09/17 18:45
字数 237
阅读 8
收藏 0

问题:

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解决:

① 输入数组允许有重复项,其他条件都不变,代码只需在原有的基础上增加一句话,while (nums[i] == nums[i + 1]) i ++; 这句话的作用是跳过树中为X的叶节点,因为它们是重复的子集,应被抛弃。

class Solution { //3ms
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums,0,list,res);
        return res;
    }
    public void dfs(int[] nums,int i,List<Integer> list,List<List<Integer>> res){
        res.add(new ArrayList<Integer>(list));
        for (int j = i;j < nums.length ;j ++ ) {
            if(j > i && nums[j] == nums[j - 1]) continue;
            list.add(nums[j]);
            dfs(nums,j + 1,list,res);
            list.remove(list.size() - 1);
        }
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
Lintcode17 Subsets solution 题解

【题目描述】 Given a set of distinct integers, return all possible subsets. Notice:Elements in a subset must be in non-descending order;The solution set must not contain duplica......

coderer
2017/04/28
0
0
Lintcode18 Subsets II solution 题解

【题目描述】 Given a list of numbers that may has duplicate numbers, return all possible subsets Notice:Each element in a subset must be in non-descending order.The ordering bet......

coderer
2017/04/29
0
0
Leetcode【78、90、289、621、718】

问题描述:【BFS、Bit】78. Subsets 解题思路: 方法1(回溯法): 这道题是给一个数组,返回所有的子集。 首先可以想到用回溯法 BFS 求解,如 nums = [0,2,5],使用回溯法可以依次得到 [0]、...

牛奶芝麻
07/03
0
0
leetcode-78-子集(用bfs解决)

题目描述: 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 示例: 输入: nums = [1,2,3]输出:[[3], [1], [2], [1,2,3], [1,3], ...

king_3
2018/08/18
0
0
划分数组为两个和相等的子集 Partition Equal Subset Sum

问题: Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. N......

叶枫啦啦
2018/01/04
500
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot 集成MongoDB

一、MongoDB 简介 MongoDB 如今是最流行的 NoSQL 数据库,被广泛应用于各行各业中,很多创业公司数据库选型就直接使用了 MongoDB,但对于大部分公司,使用 MongoDB 的场景是做大规模数据查询...

zw965
16分钟前
10
0
使用 Envoy 和 AdGuard Home 阻挡烦人的广告

> 原文链接:使用 Envoy 和 AdGuard Home 阻挡烦人的广告 通常我们使用网络时,宽带运营商会为我们分配一个 DNS 服务器。这个 DNS 通常是最快的,距离最近的服务器,但会有很多问题,比如: ...

米开朗基杨
50分钟前
16
0
springboot之全局处理异常封装

springboot之全局处理异常封装 简介 在项目中经常出现系统异常的情况,比如NullPointerException等等。如果默认未处理的情况下,springboot会响应默认的错误提示,这样对用户体验不是友好,系...

Purgeyao
今天
22
0
cookie

cookie: n. 饼干;小甜点 为什么会引入Cookie(在客户端保持http状态) 因为http协议是一种无状态协议,web服务器本身不能识别出哪些请求是同一个服务器发送的,浏览器的每一次请求都是独立...

五公里
今天
23
0
PHP常用函数

<?php/** * 获取客户端IP * @return [string] [description] */function getClientIp() { $ip = NULL; if (isset($_SERVER['HTTP_X_FORWARDED_FOR'])) { $arr = explode('......

半缘修道半缘君丶
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部