There are 2^n subsets in a powerset of a set with size n. Therefore, we iterate from [0, 2^n), and use the bits of each number to generate a subset. We generate a subset using the rule that if it is 1 on the ith bit, then we include the ith element of our original set.
class Solution {
public List<List<Integer>> subsets(int[] nums) {
int powerSetSize = (1 << nums.length);
List<List<Integer>> powerSet = new ArrayList<List<Integer>>(powerSetSize);
for(int i = 0; i < powerSetSize; i++) {
ArrayList<Integer> subset = new ArrayList<Integer>();
int n = i;
int bitIndex = 0;
while(n != 0) {
if((1 & n) == 1) {
subset.add(nums[bitIndex]);
}
bitIndex++;
n = (n >> 1);
}
powerSet.add(subset);
}
return powerSet;
}
}Questions? Have a neat solution? Comment below!