首页 > 试题广场 >

集合的子集

[编程题]集合的子集
  • 热度指数：11226 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

已知数组A和其大小n，请返回A的所有非空子集。要求A中元素个数不大于20且互异。各子集内部从大到小排序,子集间字典逆序排序。

测试样例： 
[123,456,789]
返回：{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}
算法知识视频讲解
添加回答
Java
牛客196305255号头像 牛客196305255号 
import java.util.*;
public class Subset {
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        Arrays.sort(A);
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        ArrayList<Integer> tmp=new ArrayList<>();
        solve(A,A.length-1,list,tmp);
        Collections.sort(list,new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                String s1=o2.toString().replace("[", "").replace("]", "");
                String s2=o1.toString().replace("[", "").replace("]", "");
                return s1.compareTo(s2);
            }
        });
        return list;
    }
    public static void solve(int[] A,int index,ArrayList<ArrayList<Integer>> list,ArrayList<Integer> tmp) {
        for(int i=index;i>=0;i--) {
            tmp.add(A[i]);
            list.add(new ArrayList<>(tmp));
            solve(A,i-1,list,tmp);
            tmp.remove(tmp.size()-1);
        }
    }
}

发表于 2021-02-04 14:21:09 回复(0)
Java
安徒生的谎言头像 安徒生的谎言 
import java.util.*;

import java.util.ArrayList;

public class Subset  {
    public static ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int m = (int) Math.pow(2, n);
        for (int i = m - 1; i >=1; --i) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int j = n - 1; j >= 0; --j) {
                if (((i >> j) & 1) == 1) {
                    list.add(A[j]);
                }
            }
            result.add(list);
        }
        return result;
    }
}

发表于 2018-01-29 21:48:52 回复(0)
Java
面什么过什么头像 面什么过什么 
// 因为这两个逆序，调了好久。。。
import java.util.*;

public class Subset {
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        ArrayList<ArrayList<Integer>> allSubsets = new ArrayList<ArrayList<Integer>>();
        int max = 1 << n;
        Arrays.sort(A);
        for (int k = 0; k < max; k++) {
            ArrayList<Integer> subset = convertIntToSet(k, A);
            if (subset.size() != 0) {
                allSubsets.add(0, subset);
            }
        }
        return allSubsets;
    }
    
    private ArrayList<Integer> convertIntToSet(int k, int[] A) {
        ArrayList<Integer> set = new ArrayList<Integer>();
        int index = 0;
        for (int i = k; i > 0; i >>= 1) {
            if ((i & 1) == 1) {
                set.add(0, index);
            }
            index++;
        }
        return set;
    }
}

发表于 2017-07-28 09:41:47 回复(0)
Java
牛客231395号头像 牛客231395号
import java.util.*;

public class Subset {
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList();
        if(A==null || n<1)
            return result;
        Arrays.sort(A);
        result.add(new ArrayList());
        for(int i =0;i<n;i++) {            
            int size = result.size();
            for(int j=0;j<size;j++) {
                ArrayList<Integer> list = new ArrayList(result.get(size-1));//result新加元素后，索引会变大
                list.add(0,A[i]);
                result.add(0,list);
            }
        }
        result.remove(result.size()-1);
        return result;
    }
}
编辑于 2016-07-12 17:56:52 回复(0)
提交观点

问题信息

递归
难度：
4条回答 51008浏览

热门推荐

通过挑战的用户

查看代码

相关试题

集合的子集

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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