Heim  >  Artikel  >  Java  >  Power-Set

Power-Set

DDD
DDDOriginal
2024-09-19 06:19:33451Durchsuche

Power set

Problem

Backtracking-Ansatz:
TC:(2^n) d.h. exponentielle Zeitkomplexität (Da wir bei jedem rekursiven Aufruf zwei Möglichkeiten haben, d.h. entweder den Wert bei „Index“ zu berücksichtigen oder nicht, was zu zwei möglichen Ergebnissen führt, wird dies n-mal passieren)
SC:(2^n)*(n), n für temporäre ArrayList<>() und 2^n für die Haupt-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);
    }
}

Bit-Manipulation verwenden:
TC: O(2^n)*n
SC: O(2^n)*n, (2^n für die Hauptliste und n für die Teilmengenlisten, nun, nicht alle Teilmengen werden die Größe n haben, aber wir können trotzdem davon ausgehen, dass dies der Fall ist)

Voraussetzung: Überprüfen Sie, ob das i-te Bit gesetzt ist oder nicht (weitere Einzelheiten finden Sie auf der Seite mit Tipps und Tricks zur Bitmanipulation)
Intuition:
Wenn alle nein . Teilmengen werden als Binärwerte dargestellt,
zum Beispiel: wenn n = 3, d. h. ein Array mit 3 Werten.
es wird 2^n = 8 Teilmengen geben
8 Teilmengen können auch dargestellt werden als

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

Wir werden berücksichtigen, dass, wenn der Bitwert 1 ist, dieser Indexwert in nums[] bei der Bildung der Teilmenge berücksichtigt werden sollte.
Auf diese Weise können wir alle Teilmengen erstellen

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;
    }
}

Das obige ist der detaillierte Inhalt vonPower-Set. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn