問題
回溯方法：
TC:(2^n) 即指數時間複雜度（因為我們在每次遞歸呼叫時都有兩個選擇，即要么考慮“index”處的值，要么不考慮導致2 個可能結果的值，這將發生n 次）
SC:(2^n)*(n)，n 表示暫存 ArrayList()，2^n 表示主 ArrayList();
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
powerSet(nums,0,list,new ArrayList<Integer>());
return list;
}
public void powerSet(int [] nums, int index , List<List<Integer>> list, List<Integer> 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<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
int noOfSubset = 1<<n; // this is nothing but 2^n, i.e if there are n elements in the array, they will form 2^n subsets
for(int num = 0;num<noOfSubset;num++){ /// all possible subsets numbers
List<Integer> l = new ArrayList<>();
for(int i =0;i<n;i++){// for the given subset number find which index value to pick
if((num & (1<<i))!=0) l.add(nums[i]);
}
list.add(l);
}
return list;
}
}
以上是電源組的詳細內容。更多資訊請關注PHP中文網其他相關文章！
