Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### skpro19's blog

By skpro19, history, 4 years ago, ,

• +10

 » 4 years ago, # |   0 Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).
 » 4 years ago, # |   +22 The easiest way I know is: for(int submask = mask; submask; submask = (submask - 1) & mask) { // do something } If you want 0 as a submask: for(int submask = mask; ; submask = (submask - 1) & mask) { // do something if(submask == 0) break; } You have to know if we want to do something with the submasks of every mask till 2^N the time complexity will be O(3^N) not O(4^N).
•  » » 4 years ago, # ^ |   0 Thanks man! It was really helpful.
•  » » 10 months ago, # ^ |   0 Can somebody explain please, why is it 3^n ?
•  » » » 10 months ago, # ^ | ← Rev. 4 →   +3 $3^n=\sum_{k=0}^{n} \binom{n}{k}2^k$ by binomial expansion. $2^k$ is number of submasks if we have $k$ ones. $\binom{n}{k}$ is number of masks with $k$ ones.
•  » » » » 10 months ago, # ^ | ← Rev. 4 →   0 Oh, thanks. Ive just read it here https://cp-algorithms.com/algebra/all-submasks.html :)
•  » » » » 10 months ago, # ^ |   +29 Better way to think about it is, if you have N items, then each item being considered is either 1. not in the mask, 2. in the mask but not in the submask, 3. in the submask. So 3^N.
 » 4 years ago, # | ← Rev. 2 →   +5 void rec(int start,int fin,int mask) { if(start==finish) { // masks have been generated evaluate them return; } rec(start+1,fin,mask); if(mask&(1<