Count pairs ( A , B ) such that A has X and B has Y number of set bits and A + B = C | C ++ implementation of the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 64 ] [ 64 ] [ 64 ] [ 2 ] ; int func ( int third , int seta , int setb , int carry , int number ) { if ( dp [ third ] [ seta ] [ setb ] [ carry ] != -1 ) return dp [ third ] [ seta ] [ setb ] [ carry ] ; int shift = ( number >> third ) ; if ( shift == 0 and seta == 0 and setb == 0 and carry == 0 ) return 1 ; if ( shift == 0 or seta < 0 or setb < 0 ) return 0 ; int mask = shift & 1 ; dp [ third ] [ seta ] [ setb ] [ carry ] = 0 ; if ( ( mask ) && carry ) { dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta , setb , 0 , number ) + func ( third + 1 , seta - 1 , setb - 1 , 1 , number ) ; } else if ( mask && ! carry ) { dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta - 1 , setb , 0 , number ) + func ( third + 1 , seta , setb - 1 , 0 , number ) ; } else if ( ! mask && carry ) { dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta - 1 , setb , 1 , number ) + func ( third + 1 , seta , setb - 1 , 1 , number ) ; } else if ( ! mask && ! carry ) { dp [ third ] [ seta ] [ setb ] [ carry ] += func ( third + 1 , seta , setb , 0 , number ) + func ( third + 1 , seta - 1 , setb - 1 , 1 , number ) ; } return dp [ third ] [ seta ] [ setb ] [ carry ] ; } int possibleSwaps ( int a , int b , int c ) { memset ( dp , -1 , sizeof ( dp ) ) ; int ans = func ( 0 , a , b , 0 , c ) ; return ans ; } int main ( ) { int x = 2 , y = 2 , c = 20 ; cout << possibleSwaps ( x , y , c ) ; return 0 ; }