首页 > 试题广场 >

集合的所有子集(一)

[编程题]集合的所有子集(一)
  • 热度指数：42262 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现在有一个没有重复元素的整数集合S，求S的所有子集
注意：
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素

数据范围：，集合中的任意元素满足
要求：空间复杂度 ，时间复杂度
示例1

输入

[1,2,3]

输出

[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
示例2

输入

[]

输出

[]
算法知识视频讲解
查看答案及解析
添加回答
Java
猫毛飞上天头像 猫毛飞上天
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)
Java
Sen🍓🍀头像 Sen🍓🍀 
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)
Java
牛客148901号头像 牛客148901号 
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)
Java
牛客839384289号头像 牛客839384289号 
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)
Java
向光而行的小白头像 向光而行的小白 
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)
Java
Bug专家头像 Bug专家 
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)
Java
我是菜狗呜呜呜头像 我是菜狗呜呜呜 
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)
Java
牛客575499364号头像 牛客575499364号
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 ;
    }
}
发表于 2022-02-08 10:02:55 回复(0)
Java
玄鉴头像 玄鉴 
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)
Java
合肥吴彦祖头像 合肥吴彦祖 
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)
Java
啊哈哈h头像 啊哈哈h 
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)
Java
😀offer来来来头像 😀offer来来来 
    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)
Java
可爱的猪头像 可爱的猪 
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)
Java
谁是谁的眼头像 谁是谁的眼
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);
        }
    }
}
发表于 2021-08-22 21:34:00 回复(0)
Java
WangC1117头像 WangC1117
两种方法  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)
Java
惠灵顿靖头像 惠灵顿靖 
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)
Java
又笨又懒不想上课头像 又笨又懒不想上课 
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)
Java
TheBeat头像 TheBeat
解题思路：从前往后遍历数组，每个元素有选择和不选择 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)
Java
人活着就是为了一色彩羽头像 人活着就是为了一色彩羽 
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)
Java
牛客949377463号头像 牛客949377463号 
利用位运算的性质,组合数共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条回答 23498浏览

热门推荐

通过挑战的用户

查看代码

相关试题

集合的所有子集(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号