题目描述
请编写一个方法，返回某集合的所有非空子集。
给定一个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;
}
}
