Bitmasking

What is bitmasking?
#1 it is a method of brute force (it tries all possible combinations)
#2 only use when constraints of the number are less than 20
#3 it has complexity O(2^n*n);

Can u write the first 8 numbers in binary


0 000 // {empty}
1 001 // {c}
2 010 // {b}
3 011 // {b,c}
4 100 // {a}
5 101 // {a,c}
6 110 // {a,b}
7 111	// {a,b,c}

All possible subsets of size 0 = 1 = {empty}
All possible subsets of size 1 = 3 = {a,b,c}
All possible subsets of size 2 = 3 = {no a , no b , no c}
All possible subsets of size 3 = 1 = {a,b,c}

arr = ['a','b','c']

1. left shift operator
1<<2 = 4

2. bitwise
1 & 1 = 1 ; everything else = 0;


Bitmasking code

for(int i = 0 ; i < 1<<n ; i++)
{
	for(int j = 0 ; j < n ; j++)
  {
  	if((i)&&(1<<j))  // what is this line doing ? (it checks if the jth bit is set in the number 'i')
    {
    	cout<<a[j]<<" ";
    }
  }
  cout<<endl;
}

Qn) When do you use it ?

a = [10, 20 ,30]
int flag = 1;





#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
cin >> n;
int a[n]; // wrong because if u declare array of variable size u cant initialize
int flag = 1;
for(int i= 0 ; i< n ; i++)
{
	cin>>a[i];
}
for(int i = 0 ; i < 1<<n ; i++)
{
	int sums = 0 ;
	for(int j = 0 ; j < n ; j++)
  {
  	if((i)&(1<<j))  // what is this line doing ? (it checks if the jth bit is set in the number 'i')
    {
      sums += a[j];
    } else{
    	sums -= a[j];
    }
  }

  if (sums%360 == 0){
  	flag = 0 ;
    cout<<"Yes"<<endl;
    break;
  }

}
if (flag == 1){
	cout<<"No"<<endl;
}
}


120 + 120 + 120 = 360 = 0