K | C ++ program for the above approach ; Recursive function to find the Kth smallest binary string ; Base Case ; Return string of all 1 's  of length B ; Return string of all 0 's  of length A ; Function to find the Kth lexicographically smallest binary string with exactly A zeroes and B ones ; Stores the recurring states ; Calculate the dp values iteratively ; The last character was '0' ; The last character was '1' ; Print the binary string obtained ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string KthString ( int A , int B , long long K , vector < vector < int > > & dp ) { if ( A == 0 ) { return string ( B , '1' ) ; } if ( B == 0 ) { return string ( A , '0' ) ; } if ( K <= dp [ A - 1 ] [ B ] ) { return "0" + KthString ( A - 1 , B , K , dp ) ; } else { return "1" + KthString ( A , B - 1 , K - dp [ A - 1 ] [ B ] , dp ) ; } } int KthStringUtil ( int A , int B , int K ) { vector < vector < int > > dp ( A + 1 , vector < int > ( B + 1 ) ) ; dp [ 0 ] [ 0 ] = 1 ; for ( int i = 0 ; i <= A ; ++ i ) { for ( int j = 0 ; j <= B ; ++ j ) { if ( i > 0 ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j ] ; } if ( j > 0 ) { dp [ i ] [ j ] += dp [ i ] [ j - 1 ] ; } } } cout << KthString ( A , B , K , dp ) ; return 0 ; } int main ( ) { int A = 3 , B = 3 , K = 7 ; KthStringUtil ( A , B , K ) ; return 0 ; }