Subset enumeration method

There are three kinds of subset enumeration ： Incremental construction / Bit vector method /  Binary method

And in the 《 Explain profound theories in simple language 》 Binary method is mentioned in

Binary method

Similar to bit vector method , Also enumerate the status of each location , But this time in binary , Binary length is N, Same size as the original set . The second is binary i Bit represents the... In the original set i Whether the bit is selected , Enumerate various situations . Set size is N, Namely 2 Of N Secondary mode . At this time, we should use mathematical knowledge ———— Combine 、 Complement set 、 intersection 、 contain 、 Belong to etc .

• set up A、B Is the binary representation of two sets , be

  • The intersection is expressed as A & B
  • Union is expressed as A | B
  • The symmetric difference set is expressed as A ^ B
  • The complement is expressed as ALL ^ A [ among ALL = (1 << n) - 1]

• [ Enumerate all subsets ]：
  enumeration 0 To (1 << n) - 1 Every number in i, Then put the numbers i Convert to binary ,
  If i Of the j Is it 1, Represents a collection i contain a[j];
  If i Of the j Is it 0, Represents a collection i It doesn't contain a[j].

　　 Templates

• Print digit i Represents a collection of

1 2 3 4 5 6 7 8

intn, a[maxn];  // The length is n Sequence voidprint_subset(ints){  // Print s The subset represented     for(inti = 0; i < n; i ++){         if(s & (1<< i)) cout << a[i] << " ";     }     cout << endl; }

• Enumerate all subsets

1 2 3 4 5

voidsolve() {     for(inti = 0; i < (1<< n); i ++) {         print_subset(i);  // Use binary numbers i Represents a subset     } }

• Enumerate all sizes k Subset

1 2 3 4 5 6 7

voidsolve(intk) {     for(inti = (1<< k) - 1; i < (1<< n);) {         print_subset(i);         intx = i & -i, y = i + x;         i = (((i & ~y) / x ) >> 1) | y;     } }

• [ Enumerate a given set x All subsets of ]

1 2 3 4 5

voidsolve(intx) {     for(inti = x; i >= 0; i = (i - 1) & x) {         print_subset(i);     } }