题目描述
请编写一个方法，返回某集合的所有非空子集。
给定一个int数组A和数组的大小int n，请返回A的所有非空子集。保证A的元素个数小于等于20，且元素互异。各子集内部从大到小排序,子集之间字典逆序排序。
/* *思路：集合A中的每个元素在子集中有两种状态：取或不取 *因此，可以用n位的二进制数（n为A中元素个数）表示集合A中元素在子集中的状态 *即，二进制数1到(2^n)-1表示了A的子集的所有情况 *举个例子A = [2, 1] *二进制数: *11表示子集[2, 1] *10表示[2] *01表示[1] */ public class Subset {
public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
Arrays.sort(A); //将数组A升序排序 ArrayList<ArrayList<Integer>> result = new ArrayList<>(); int count = (int) (Math.pow(2, A.length) - 1); //count为2^n - 1 for(int i = count; i > 0; i--) {
//count递减遍历所有子集情况 ArrayList<Integer> temp = new ArrayList<>(); //temp保存该次得到的子集 //这里用右移判断二进制数的最后一位是1还是0，为1表示A[cn]取，0表示A[cn]不取 for(int j = i,cn = 0; j > 0; j >>= 1, cn++) {
if((j & 1) == 1) {
temp.add(0, A[cn]); //这里注意题目要求的是逆序输出，所以应该将A[cn]插入到temp的第0位 } } result.add(temp); } return result; } } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/125519.html