首页 技术 正文
技术 2022年11月23日
0 收藏 369 点赞 2,734 浏览 844 个字

一. 问题描述

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: [1,2,2]

输出:

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

二. 解题思路

本题思路:采用回溯算法进行求解,构建递归函数(全局变量列表data存储子集,局部变量list存储当前某一个具体子集,n表示添加的位数,nums全局数组)

步骤一:将数组nums从小到大进行排序。

步骤二:构建递归函数,判断list对象是否已经存在于data中,如果不存在则添加,则否跳过。

步骤三:根据n的位置继续添加未加入到list的数字,并且返回步骤二进行递归。

步骤四:得到data列表,返回data。

三. 执行结果

执行用时 :17 ms, 在所有 java 提交中击败了9.14%的用户

内存消耗 :36.6 MB, 在所有 java 提交中击败了94.59%的用户

四. Java代码

class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> data=new ArrayList<List<Integer>>();
List<Integer> list=new ArrayList<Integer>();
sw(data,list,0,nums);
return data;
} public void sw(List<List<Integer>> data,List<Integer> list,int n,int[] nums)
{
if(!data.contains(list))
{
data.add(list);
}
for(int i=n;i<nums.length;i++)
{
List<Integer> alist=new ArrayList<Integer>(list); alist.add(nums[i]);
sw(data,alist,i+1,nums);
}
}
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102