GEnerare submultimi cu 2 for complexitate O(n2^n)

submultimi.java

/*
for(int i = 1; i <= n; ++i) {
	   for(int j = 1; j <= n; ++j) {

	   }
}

O(n^2)


A = {1,2,3};

Toate submultimile = 2^n = 2^3 = 8 submultimi

Time Complexity O(n 2^n)
0000 0000 0000 0000 0000 0000 0000 0001

1 = 001 {1}  
2 = 010 {2}
3 = 011 {1,2}
4 = 100 {3}
5 = 101 {1,3}
6 = 110 {3,2}
7 = 111  {1,2,3}
8 = 1000 {}

0000 0000 0000 0000 0000 0000 0000 1000 = 8

001 &
001
===
001 

001 SAU
010
===
011 


*/

//pow(2,n)


public class Subsets {

   public static void gen(int n) {

     for(int mask = 1; mask<= (1<<n); mask++) {

	      System.out.print("{");

	      for(int i = 0; i < n; i++) {

               if((mask & (1<<i)) != 0) {

               	     System.out.print(i + 1 + " ");
               }

	       }

    	 System.out.println("}");

     }	 

   }	 

   //5 = 101 {1,3}
   //    101
   //    100   

   public static void main(String[] args) {

        int n = 3;
        gen(n);

   }

}