问题
回溯方法：
tc:(2^n) 即指数时间复杂度（因为我们在每次递归调用时都有两个选择，即要么考虑“index”处的值，要么不考虑导致 2 种可能结果的值，这将发生 n 次）
sc:(2^n)*(n)，n 表示临时 arraylist() ， 2^n 表示主 arraylist();
class solution {
public list> subsets(int[] nums) {
list> list = new arraylist<>();
powerset(nums,0,list,new arraylist());
return list;
}
public void powerset(int [] nums, int index , list> list, list l){
//base case
if(index ==nums.length){
list.add(new arraylist<>(l));
return;
}
//take
l.add(nums[index]); //consider the value at 'index'
powerset(nums,index+1,list,l);
//dont take;
l.remove(l.size()-1);// don't consider the value at 'index'
powerset(nums,index+1,list,l);
}
}
使用位操作：
tc：o(2^n)*n
sc：o(2^n)*n，（2^n 表示主列表，n 表示子集列表，并不是所有子集的大小都是 n，但我们仍然可以假设情况是这样）
先决条件：检查第i位是否已设置（有关更多详细信息，请参阅位操作提示和技巧页面）
直觉：
如果全都没有。子集表示为二进制值，
例如：如果 n = 3，即数组中有 3 个值。
将有 2^n = 8 个子集
8个子集也可以表示为
| index 2 | index 1 | index 0 | subset number |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
| 1 | 0 | 0 | 4 |
| 1 | 0 | 1 | 5 |
| 1 | 1 | 0 | 6 |
| 1 | 1 | 1 | 7 |
我们将考虑到，如果位值为 1，则应考虑 nums[] 中的索引值来形成子集。
这样我们就能够创建所有子集
class Solution {
public List> subsets(int[] nums) {
List> list = new ArrayList<>();
int n = nums.length;
int noOfSubset = 1< l = new ArrayList<>();
for(int i =0;i
