注意：
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素
数据范围：
，集合中的任意元素满足 
要求：空间复杂度 )
，时间复杂度
[编程题]集合的所有子集(一)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S int整型一维数组
* @return int整型ArrayList<ArrayList<>>
*/
ArrayList<ArrayList<Integer>> res;
public ArrayList<ArrayList<Integer>> subsets (int[] S) {
// write code here
ArrayList<Integer> list = new ArrayList<>();
Arrays.sort(S);
res = new ArrayList<>();
backtrace(0,S,list);
Collections.sort(res,new Comparator<ArrayList<Integer>>(){
public int compare(ArrayList<Integer> list1,ArrayList<Integer>list2){
return list1.size()-list2.size();
}
});
return res;
}
public void backtrace(int k,int[]S,ArrayList<Integer>list){
res.add(new ArrayList<>(list));
for(int i = k; i < S.length; i++){
list.add(S[i]);
backtrace(i+1,S,list);
list.remove(list.size()-1);
}
}
}
发表于 2025-05-28 10:56:44
回复(0)
import java.util.*;
// 回溯
public class Solution {
private ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 结果集
private ArrayList<Integer> path = new ArrayList<>(); // 一次路径
public ArrayList<ArrayList<Integer>> subsets (int[] S) {
// write code here
if (S.length == 0) return res;
Arrays.sort(S); // 排序
backtrack(S, 0); // 调用
res.sort((list1, list2)-> { // 结果集 排序
int m = list1.size(), n = list2.size();
if (m != n) return m - n;
for (int i = 0; i < n; i++) {
if (list1.get(i) == list2.get(i)) continue;
return list1.get(i) - list2.get(i);
}
return 114514; // 不会到这
});
return res;
}
// 回溯
private void backtrack(int[] S, int k) {
if (k == S.length) {
res.add(new ArrayList<>(path));
return;
}
// 不选
backtrack(S, k + 1);
// 选
path.add(S[k]);
backtrack(S, k + 1);
path.remove(path.size() - 1);
}
}
发表于 2025-03-28 17:07:53
回复(0)
import java.util.*;
public class Solution {
public void backtrack(int[] nums, int start, ArrayList<Integer> subset,
ArrayList<ArrayList<Integer>> result) {
result.add(new ArrayList<>(subset));
for (int i = start; i < nums.length; i++) {
subset.add(nums[i]);
backtrack(nums, i + 1, subset, result);
subset.remove(subset.size() - 1);
}
}
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
result.sort(Comparator.comparingInt((ArrayList<Integer> a) ->
a.size()).thenComparingInt(a -> a.get(0)));
return result;
}
}
发表于 2024-05-09 23:05:30
回复(0)
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> subsets (int[] S) {
// write code here
Arrays.sort(S);
recur(S ,new ArrayList<Integer>() ,0);
return res;
}
public void recur(int[] arr ,ArrayList<Integer> list ,int index){
res.add(new ArrayList<Integer>(list));
for(int i=index;i<arr.length;i++){
list.add(arr[i]);
recur(arr ,list ,i+1);
list.remove(list.size()-1);
}
}
编辑于 2024-03-10 13:08:48
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
int n = S.length;
ArrayList<ArrayList<Integer>>ans = new ArrayList<>();
ans.add(new ArrayList<Integer>());
for (int i = 0; i < n; i++) {
int size = ans.size();
for (int j = 0; j < size; j++) {
ArrayList<Integer>path = new ArrayList<Integer>();
path.addAll(ans.get(j));
path.add(S[i]);
ans.add(path);
}
}
int size=ans.size();
for (int i = 0; i <size - 1; i++)
// Last i elements are already in place
for (int j = 0; j < size - i - 1; j++)
if (ans.get(j).size() > ans.get(j+1).size()){
ArrayList<Integer>tmp=new ArrayList<>();
tmp=ans.get(j);
ans.set(j,ans.get(j+1));
ans.set(j+1,tmp);
}
return ans;
}
}
发表于 2023-02-02 04:30:37
回复(0)
import java.util.*;
//位运算求全子集
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if(S==null||S.length==0) return ans;
//由于要子集当中的元素升序，所以可以先对S排序，最后子集当中求出的子集内部就是有序的。
Arrays.sort(S);
int len = S.length;
int num = (int)Math.pow(2,len);
for(int i = 0;i<num;i++){
ArrayList<Integer> ls = new ArrayList<Integer>();
int count = 0;
int flag = i;
while(flag!=0){
int index = flag&1;
if(index==1) ls.add(S[count]);
flag = flag>>1;
count++;
}
ans.add(ls);
}
return ans;
}
}
发表于 2022-07-16 11:04:21
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(S == null) return res;
backtrack(res, S, 0, new ArrayList<>());
return res;
}
public void backtrack(ArrayList<ArrayList<Integer>> res, int[] S, int index, ArrayList<Integer> list){
res.add(new ArrayList<>(list));
for(int i = index; i < S.length; i++){
list.add(S[i]);
backtrack(res, S, i + 1, list);
list.remove(list.size() - 1);
}
}
}
发表于 2022-04-24 17:27:02
回复(0)
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> r = new ArrayList() ;
int l = 2 << (S.length-1) ;
for(int i = 0 ; i < l ; i ++) {
ArrayList<Integer> c = new ArrayList() ;
for(int j = 0 ; j < S.length ; j ++ ) {
if( ((i>>j)&1) == 1) c.add(S[j]);
}
r.add(c);
}
return r ;
}
}
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> r = new ArrayList() ;
int l = 2 << (S.length-1) ;
for(int i = 0 ; i < l ; i ++) {
ArrayList<Integer> c = new ArrayList() ;
for(int j = 0 ; j < S.length ; j ++ ) {
if( ((i>>j)&1) == 1) c.add(S[j]);
}
r.add(c);
}
return r ;
}
}
发表于 2022-02-08 10:02:55
回复(0)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
Arrays.sort(S);
int n=S.length;
dfs(S,0,new ArrayList<Integer>());
return res;
}
public void dfs(int[]s,int index,ArrayList<Integer> temp){
res.add(new ArrayList<Integer>(temp));
for(int i=index;i<s.length;i++){
temp.add(s[i]);
dfs(s,i+1,temp);
temp.remove(temp.size()-1);
}
}
}
发表于 2022-01-01 12:13:04
回复(0)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
List<Integer> list = new LinkedList<>();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
dfs(S,0);
return ans;
}
void dfs(int[] nums, int index){
ans.add(new ArrayList(list));
for(int i = index; i< nums.length; i++){
list.add(nums[i]);
dfs(nums,i+1);
list.remove(list.size() - 1);
}
}
}
发表于 2021-12-03 11:20:42
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
if(S==null || S.length==0) return res;
Arrays.sort(S);
dfs(S,0,new ArrayList<Integer>(),res);
return res;
}
private void dfs(int[] nums,
int startIndex,
ArrayList<Integer> subset,
ArrayList<ArrayList<Integer>> res){
res.add(new ArrayList<Integer>(subset));//深复制
// res.add(subset);
for(int i=startIndex;i<nums.length;i++){
subset.add(nums[i]);
// ArrayList<Integer> newSet = new ArrayList<Integer>(subset);
// newSet.add(nums[i]);
// dfs(nums,i+1,newSet,res);
dfs(nums,i+1,subset,res);
subset.remove(subset.size()-1);
}
}
}
发表于 2021-11-09 10:16:21
回复(0)
ArrayList<ArrayList<Integer>> res;
ArrayList<Integer> temp;
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
res = new ArrayList<>();
int n=S.length;
if(S==null || n==0){
res.add(new ArrayList<>());
return res;
}
temp = new ArrayList<>();
dfs(S,0);
res.sort(new Comparator<ArrayList<Integer>>(){
@Override
public int compare(ArrayList<Integer> l1,ArrayList<Integer> l2){
int num1 = l1.size()-l2.size();
if(num1==0){
int num2=0;
for(int i=0;i<l1.size();i++){
if(l1.get(i)!=l2.get(i)){
num2 = l1.get(i)-l2.get(i);
}
}
return num2;
}
else{
return num1;
}
}
});
return res;
}
public void dfs(int[] S,int index){
if(index>S.length) return;
if(index==S.length) {res.add(new ArrayList<>(temp));return;}
temp.add(S[index]);
dfs(S,index+1);
temp.remove(temp.size()-1);
dfs(S,index+1);
}
发表于 2021-09-04 14:54:55
回复(0)
import java.util.*;
// 使用BFS实现所有子集有序
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> ansLists = new ArrayList<>();
ansLists.add(new ArrayList<>());
if(S==null || S.length==0) return ansLists;
Queue<List<Integer>> queue = new LinkedList<>();
for(int i=0; i<S.length; i++) {
ArrayList<Integer> tmp = new ArrayList<>();
tmp.add(i);
queue.add(tmp);
}
while(!queue.isEmpty()) {
int size = queue.size();
for(int i=0; i<size; i++) {
List<Integer> head = queue.poll();
ansLists.add(new ArrayList<>(head));
for(int j=head.get(head.size()-1)+1; j<S.length; j++) {
head.add(j);
queue.add(new ArrayList<>(head));
head.remove(head.size()-1);
}
}
}
for(List<Integer> list: ansLists) {
for(int i=0; i<list.size(); i++) {
list.set(i, S[list.get(i)]);
}
}
return ansLists;
}
}
发表于 2021-08-23 11:01:54
回复(0)
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
helper(S,new ArrayList<Integer>(),-1);
return res;
}
public void helper(int[] nums,ArrayList<Integer> path,int start){
res.add(new ArrayList(path));
for(int i = start+1; i < nums.length; i++){
path.add(nums[i]);
helper(nums,path,i);
path.remove(path.size()-1);
}
}
}
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
helper(S,new ArrayList<Integer>(),-1);
return res;
}
public void helper(int[] nums,ArrayList<Integer> path,int start){
res.add(new ArrayList(path));
for(int i = start+1; i < nums.length; i++){
path.add(nums[i]);
helper(nums,path,i);
path.remove(path.size()-1);
}
}
}
发表于 2021-08-22 21:34:00
回复(0)
两种方法 1. 回溯
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> lll = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
lll.add(list);
huiSu(S,list,0, lll);
return lll;
}
public void huiSu(int[] S, ArrayList<Integer> ll, int i, ArrayList<ArrayList<Integer>> lll){
for(; i < S.length; i++){
ArrayList<Integer> list = new ArrayList<>(ll);
list.add(S[i]);
lll.add(list);
huiSu(S, list, i+1, lll);
}
} 2. 位运算public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> lll = new ArrayList<>();
int end = 1 << S.length;
for (int i = 0; i < end; i++){
ArrayList<Integer> list = new ArrayList<>();
for(int j = 0; j< S.length; j++){
if((1<<j & i) !=0){
list.add(S[j]);
}
}
lll.add(list);
}
return lll;
}
发表于 2021-08-05 16:39:27
回复(3)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> ls = new ArrayList();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
//保证了不会重复访问
int[] used = new int[S.length];
Arrays.sort(S);
dfs(S,used,0);
return res;
}
private void dfs(int[] a,int[] used,int start) {
//这一步没有return; 保证了将每个遍历到的都输出一遍
res.add(new ArrayList(ls));
for(int i = start; i < a.length; i++) {
if(used[i] == 1) continue;
ls.add(a[i]);
used[i] = 1;
dfs(a,used,i);
ls.remove(ls.size()-1);
used[i] = 0;
}
}
}
发表于 2021-07-15 21:57:51
回复(0)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> ls = new ArrayList();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
int[] used = new int[S.length];
Arrays.sort(S);
dfs(S,used,0);
return res;
}
private void dfs(int[] a,int[] used,int start) {
res.add(new ArrayList(ls));
for(int i = start; i < a.length; i++) {
if(used[i] == 1) continue;
ls.add(a[i]);
used[i] = 1;
dfs(a,used,i);
ls.remove(ls.size()-1);
used[i] = 0;
}
}
}
发表于 2021-06-17 10:52:27
回复(0)
解题思路：从前往后遍历数组，每个元素有选择和不选择 2种状态。
1、选择第i个元素：此时组合结果为=原来的组合 U 原来每一个组合加上元素i 的组合 。
2、不选择第i个元素：此时组合结果不变。
设f(i)表示前i个元素的组合。初始条件 f(0) =[ [] ] ;
f(i) = f(i-1) U foreach(f(i-1)) { f(i-1) U s[i] } U表示并集
import java.util.*;
public class Solution {
ArrayList<Integer> subResult = new ArrayList();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
// 升序排列
Arrays.sort(S);
ArrayList<ArrayList<Integer>> result = new ArrayList();
ArrayList<Integer> subResult = new ArrayList();
// 一个都不选择
result.add(subResult);
for(int i = 0 ; i< S.length; i++){
// 选择S[i]时，才会增加状态 原先的SubResult 每个增加一个S[i];
ArrayList<ArrayList<Integer>> newResult = new ArrayList();
for(ArrayList<Integer> lastSubResult : result){
ArrayList<Integer> newSubResult = new ArrayList();
newSubResult.addAll(lastSubResult);
newSubResult.add(S[i]);
newResult.add(newSubResult);
}
result.addAll(newResult);
}
return result;
}
}
编辑于 2021-06-09 23:53:05
回复(0)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> arrays = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<Integer> array = new ArrayList<Integer>();
if (S.length == 0){
arrays.add(array);
}
Arrays.sort(S);
function(S,0,S.length - 1,array);
return arrays;
}
public void function(int[] arr,int start,int end,ArrayList<Integer> array){
if (!arrays.contains(new ArrayList<Integer>(array))){
arrays.add(new ArrayList<Integer>(array));
}
if (start > end){
return ;
}
array.add(arr[start]);
function(arr,start + 1,end,array);
array.remove(array.size() -1);
function(arr,start + 1,end,array);
}
}
发表于 2021-04-18 17:38:09
回复(0)
利用位运算的性质,组合数共2^n个,用迭代，某位为1就代表取这个值，为0代表不取public ArrayList<ArrayList<Integer>> subsets(int[] S) { int size = 1 << S.length; ArrayList<ArrayList<Integer>> res = new ArrayList<>(size); for (int i = 0; i < size; i++) { res.add(process(i, S)); } return res; } private ArrayList<Integer> process(int index, int[] S){ ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < S.length; i++) { int bit = index >>> i; if((bit & 1) == 1) { list.add(S[i]); } } return list; }
编辑于 2021-04-04 13:59:55
回复(0)
问题信息
难度：
33条回答
423收藏
24490浏览
通过挑战的用户
查看代码-
2022-09-20 16:05:50
-
2022-09-15 14:34:59 -
2022-09-15 14:01:21 -
2022-09-15 10:56:24 -
2022-09-14 21:34:42
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
