Maximum subset sum such that no two elements in set have same digit in them | Javascript implementation of above approach ; Function to create mask for every number ; Recursion for Filling DP array ; Base Condition ; Recurrence Relation ; Function to find Maximum Subset Sum ; Initialize DP array ; Iterate over all possible masks of 10 bit number ; Driver Code
let dp = new Array ( 1024 ) ; dp . fill ( - 1 ) ; function get_binary ( u ) { let ans = 0 ; while ( u > 0 ) { let rem = u % 10 ; ans |= ( 1 << rem ) ; u = parseInt ( u / 10 , 10 ) ; } return ans ; } function recur ( u , array , n ) { if ( u == 0 ) return 0 ; if ( dp [ u ] != - 1 ) return dp [ u ] ; for ( let i = 0 ; i < n ; i ++ ) { let mask = get_binary ( array [ i ] ) ; if ( ( mask u ) == u ) { dp [ u ] = Math . max ( Math . max ( 0 , dp [ u ^ mask ] ) + array [ i ] , dp [ u ] ) ; } } return dp [ u ] ; } function solve ( array , n ) { for ( let i = 0 ; i < ( 1 << 10 ) ; i ++ ) { dp [ i ] = - 1 ; } let ans = 0 ; for ( let i = 0 ; i < ( 1 << 10 ) ; i ++ ) { ans = Math . max ( ans , recur ( i , array , n ) ) ; } return ans ; } let array = [ 22 , 132 , 4 , 45 , 12 , 223 ] ; let n = array . length ; document . write ( solve ( array , n ) ) ;