集合的所有子集(一)_

Java

牛客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专家

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号

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

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来来来

    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

两种方法 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

解题思路：从前往后遍历数组，每个元素有选择和不选择 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号

利用位运算的性质,组合数共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)

Java

花落梦里

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    ArrayList<Integer>temp=new ArrayList<>();
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);//先排一下序
        dfs(S,0);
        sort(res);
        return res;
    }
   
    public void dfs(int[]S, int index){
        if(index==S.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        dfs(S,index+1);
        temp.add(S[index]);
        dfs(S,index+1);
        temp.remove(temp.size()-1);
    }
    public void sort(ArrayList<ArrayList<Integer>> res){
        Collections.sort(res, new Comparator<ArrayList<Integer>>(){//主要是排序最后的结果。。。。
            public int compare(ArrayList<Integer> list1, ArrayList<Integer> list2){
                if(list1.size() > list2.size()){
                    return 1;
                }
                else if(list1.size() < list2.size()){
                    return -1;
                }
                else{
                    return 0;
                }
            }
        });
    }
}

发表于 2021-03-26 15:15:43 回复(1)

Java

-SoFar°

    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        if (S==null||S.length==0) return new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Arrays.sort(S);//升序排序数组
        dfs(0, S, list, res);
        //对结果集进行排序 每个list外部排序 内部一定是有序的 因为dfs搞好了已经
        //list外部排序主要看长度 短的在前面
        Collections.sort(res, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> list1, ArrayList<Integer> list2) {
                //我想要短的在前面  或者说 升序 那就是长度size 左-右
                return list1.size()-list2.size();
            }
        });
        return res;
    }

    private void dfs(int level, int[] s, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> res) {
        if (level == s.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        //业务逻辑：子集问题就是一个分支：递归不选当前数直接下探 另一个分支：递归选当前数再下探
        //分支1：如果选当前level为索引下的数  排序输出 没办法 必须先选
        list.add(s[level]);
        dfs(level + 1, s, list, res);
        list.remove(list.size() - 1);

        //分支2：如果不选当前level为索引下的数 就直接从这里下探了 直到level大于len 逐层返回
        dfs(level + 1, s, list, res);
    }

发表于 2021-03-21 19:39:18 回复(0)

Java

so_what_xxxx

//无栈才是快的 BFS典型应用

public class Solution {

private ArrayList<ArrayList<Integer>> res=null;
private ArrayList<Integer> temp=null;
    private int[] num=null;
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
         this.res=new ArrayList<>();
      this.temp=new ArrayList<>();
      Arrays.sort(S);
      this.num=S;
      res.add(new ArrayList<>(temp));
      LinkedList<ArrayList<Integer>> queue1=new LinkedList<>();
      LinkedList<Integer> queue2=new LinkedList<>();
      queue1.addLast(temp);
      queue2.addLast(0);
      while(!queue1.isEmpty()) {
           this.temp=queue1.removeFirst();
           int start=queue2.removeFirst();
           for(int i=start;i<num.length;i++) {
      temp.add(num[i]);
      ArrayList<Integer> ele=new ArrayList<>(temp);
      res.add(ele);
      queue1.addLast(ele);
      queue2.addLast(i+1);
      temp.remove(temp.size()-1);
      }
      }
      return res;
}
}

发表于 2021-02-20 23:23:37 回复(0)

集合的所有子集(一)

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题