Ensemble de puissance

Problème

Approche de retour en arrière :
TC:(2^n) c'est-à-dire une complexité temporelle exponentielle (puisque nous avons deux choix à chaque appel récursif, c'est-à-dire soit considérer la valeur à « index » ou non, ce qui conduit à 2 résultats possibles, cela se produira n fois)
SC:(2^n)*(n), n pour temp ArrayList<>() et 2^n pour ArrayList principal<>();

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

---

Utilisation de la manipulation de bits :
TC : O(2^n)*n
SC : O(2^n)*n, (2^n pour la liste principale et n pour les listes de sous-ensembles, eh bien, tous les sous-ensembles ne seront pas de taille n mais nous pouvons quand même supposer que c'est le cas)

pré-requis : vérifier si le bit est activé ou non (référez-vous à la page Trucs et astuces sur la manipulation des bits pour plus de détails)
Intuition :
Si tout le non. les sous-ensembles sont représentés sous forme de valeurs binaires,
par exemple : si n = 3, c'est-à-dire un tableau contenant 3 valeurs.
il y aura 2^n = 8 sous-ensembles
8 sous-ensembles peuvent également être représentés comme

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

Nous prendrons en considération le fait que si la valeur du bit est 1, alors cette valeur d'index dans nums[] doit être prise en compte pour former le sous-ensemble.
De cette façon nous pourrons créer tous les sous-ensembles

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!