首頁  >  文章  >  Java  >  電源組

電源組

DDD
DDD原創
2024-09-19 06:19:33476瀏覽

Power set

問題

回溯方法:
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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn