title: Inclusion-exclusion in dynamic programming
body: <p>There are N soldiers (numbered from 1 to N). Each soldier has some subset of skills out of M different skills (numbered from 1 to M). The skill-set of an army is the union of skill-sets of its constituent soldiers. How many different subsets of soldiers satisfy are there which have specific skill-set requirement <br><br></p>
  
  <p><a href="https://www.hackerrank.com/contests/w16/challenges/vim-war" rel="noreferrer">Problem Link</a><br><br><br></p>
  
  <p>According to the Explanation problem reduces to finding the number of subsets of these numbers whose OR is exactly equal to the required value, say req</p>
  
  <p><br><Br>
  Let f(i) be the number of numbers j such that j OR i = i.<br><br>Then the answer is<br>
  <strong>∑i(−1)^popcount(i xor req)(2^f(i)−1) for all i such that i OR req is req</strong></p>
  
  <p><br><br>Please Explain the above formula and How it came<br><br>I know No. of ways to choose N element is (2^n-1) but why this term <code>(−1)^popcount(i xor req)</code></p>
  
  <p>Please Explain the algorithm.</p>