Count pairs ( A , B ) such that A has X and B has Y number of set bits and A + B = C | Initial DP array ; Recursive function to generate all combinations of bits ; if the state has already been visited ; find if C has no more set bits on left ; if no set bits are left for C and there are no set bits for A and B and the carry is 0 , then this combination is possible ; if no set bits are left for C and requirement of set bits for A and B have exceeded ; Find if the bit is 1 or 0 at third index to the left ; carry = 1 and bit set = 1 ; since carry is 1 , and we need 1 at C 's bit position we can use 0 and 0  or 1 and 1 at A and B bit position ; carry = 0 and bit set = 1 ; since carry is 0 , and we need 1 at C 's  bit position we can use 1 and 0  or 0 and 1 at A and B bit position ; carry = 1 and bit set = 0 ; since carry is 1 , and we need 0 at C 's  bit position we can use 1 and 0  or 0 and 1 at A and B bit position ; carry = 0 and bit set = 0 ; since carry is 0 , and we need 0 at C 's  bit position we can use 0 and 0  or 1 and 1 at A and B bit position ; Function to count ways ; function call that returns the answer ; Driver Code
dp = [ [ [ [ - 1 , - 1 ] for i in range ( 64 ) ] for j in range ( 64 ) ] for k in range ( 64 ) ] NEW_LINE def func ( third , seta , setb , carry , number ) : NEW_LINE INDENT if dp [ third ] [ seta ] [ setb ] [ carry ] != - 1 : NEW_LINE INDENT return dp [ third ] [ seta ] [ setb ] [ carry ] NEW_LINE DEDENT shift = number >> third NEW_LINE if ( shift == 0 and seta == 0 and setb == 0 and carry == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( shift == 0 or seta < 0 or setb < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT mask = shift & 1 NEW_LINE dp [ third ] [ seta ] [ setb ] [ carry ] = 0 NEW_LINE if ( mask ) and carry : NEW_LINE INDENT dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta , setb , 0 , number ) + func ( third + 1 , seta - 1 , setb - 1 , 1 , number ) NEW_LINE DEDENT elif mask and not carry : NEW_LINE INDENT dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta - 1 , setb , 0 , number ) + func ( third + 1 , seta , setb - 1 , 0 , number ) NEW_LINE DEDENT elif not mask and carry : NEW_LINE INDENT dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta - 1 , setb , 1 , number ) + func ( third + 1 , seta , setb - 1 , 1 , number ) NEW_LINE DEDENT elif not mask and not carry : NEW_LINE INDENT dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta , setb , 0 , number ) + func ( third + 1 , seta - 1 , setb - 1 , 1 , number ) NEW_LINE DEDENT return dp [ third ] [ seta ] [ setb ] [ carry ] NEW_LINE DEDENT def possibleSwaps ( a , b , c ) : NEW_LINE INDENT ans = func ( 0 , a , b , 0 , c ) NEW_LINE return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x , y , c = 2 , 2 , 20 NEW_LINE print ( possibleSwaps ( x , y , c ) ) NEW_LINE DEDENT