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
using System ; class GFG { static int [ , , , ] dp = new int [ 64 , 64 , 64 , 2 ] ; static int func ( int third , int seta , int setb , int carry , int number ) { if ( third > - 1 && seta > - 1 && setb > - 1 && carry > - 1 ) if ( dp [ third , seta , setb , carry ] != - 1 ) return dp [ third , seta , setb , carry ] ; int shift = ( number >> third ) ; if ( shift == 0 && seta == 0 && setb == 0 && carry == 0 ) return 1 ; if ( shift == 0 seta < 0 setb < 0 ) return 0 ; int mask = shift & 1 ; dp [ third , seta , setb , carry ] = 0 ; if ( ( mask == 1 ) && carry == 1 ) { dp [ third , seta , setb , carry ] += func ( third + 1 , seta , setb , 0 , number ) + func ( third + 1 , seta - 1 , setb - 1 , 1 , number ) ; } else if ( mask == 1 && carry == 0 ) { dp [ third , seta , setb , carry ] += func ( third + 1 , seta - 1 , setb , 0 , number ) + func ( third + 1 , seta , setb - 1 , 0 , number ) ; } else if ( mask == 0 && carry == 1 ) { dp [ third , seta , setb , carry ] += func ( third + 1 , seta - 1 , setb , 1 , number ) + func ( third + 1 , seta , setb - 1 , 1 , number ) ; } else if ( mask == 0 && carry == 0 ) { 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 ] ; } static int possibleSwaps ( int a , int b , int c ) { for ( int q = 0 ; q < 64 ; q ++ ) { for ( int r = 0 ; r < 64 ; r ++ ) { for ( int p = 0 ; p < 64 ; p ++ ) { for ( int d = 0 ; d < 2 ; d ++ ) { dp [ q , r , p , d ] = - 1 ; } } } } int ans = func ( 0 , a , b , 0 , c ) ; return ans ; } public static void Main ( String [ ] args ) { int x = 2 , y = 2 , c = 20 ; Console . WriteLine ( possibleSwaps ( x , y , c ) ) ; } }