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!