这道题也是子集问题，与子集-II是同类型的题目。
0x1 题目详情
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
测试用例:
输入： nums = [1,2,3] 输出： [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] ]
0x2 解题思路
思路一:
这道题我的第一想法不就是从左往右单向的递归模型吗？想都不用想。
对于每一个数，我们都有两种选择：
递归的base case就是当我们的下标已经达到最大时，停止递归。时间复杂度为$O(N)$,因为递归终止时我们扫描了一遍数组。
递归
思路二:
采用位运算，我们可以使用1个bit代表数组的中一个数，因为1个bit的状态只有两种，每个数选择不选择的状态也只有两种，与上边讲得递归状态一致。 求幂集就是在对应bit数组成的不同的二进制数中，把每个二进制数中bit状态为1的数加入当前结果集。然后处理完一个二进制数后把当前结果集加入最后的结果集即可。(其中讲二进制数是不准确的，应该是组成的不同数中)。
以长度为2的数组为例：两位bit能够组成的数有四个：00、01、10、11，对应的结果集[[],[2],[1],[1,2]]。
0x3 代码实现
递归法：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
if(nums== null || nums.length==0){
result.add(new ArrayList<Integer>());
return result;
}
List<Integer> curResult=new ArrayList<>();
recur(nums,0,curResult,result);
return result;
}
private void recur(int[] nums,int index,List<Integer> curResult,List<List<Integer>> result){
if(index== nums.length){
result.add(curResult);
return;
}
//不要当前元素
recur(nums,index+1,curResult,result);
//要当前元素
List<Integer> temp=new ArrayList<>(curResult);
temp.add(nums[index]);
recur(nums,index+1,temp,result);
}
}
位运算：我咋感觉时间复杂度还高了？
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
if(nums== null){
return result;
}
//需要求出个数为nums.length的bit数能够组成的二进制数的个数
int power=(int)Math.pow(2,nums.length);
for(int i=0;i<power;i++){
List<Integer> curResult=new ArrayList<>();
//j代表右移的位数
for(int j=0;j<nums.length;j++){
if(((i>>>j)&1)==1){
curResult.add(nums[j]);
}
}
result.add(curResult);
}
return result;
}
}
0x4 课后总结
递归方法很简单没什么好说了，倒是位运算的方法给我了一种新的思路。
如果递归时一个数的状态只有两种，那么就可以把递归改成位运算的实现方法。