Maximum subset sum such that no two elements in set have same digit in them | Java 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
import java . io . * ; class GFG { static int [ ] dp = new int [ 1024 ] ; static int get_binary ( int u ) { int ans = 0 ; while ( u > 0 ) { int rem = u % 10 ; ans |= ( 1 << rem ) ; u /= 10 ; } return ans ; } static int recur ( int u , int [ ] array , int n ) { if ( u == 0 ) return 0 ; if ( dp [ u ] != - 1 ) return dp [ u ] ; for ( int i = 0 ; i < n ; i ++ ) { int 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 ] ; } static int solve ( int [ ] array , int n ) { for ( int i = 0 ; i < ( 1 << 10 ) ; i ++ ) { dp [ i ] = - 1 ; } int ans = 0 ; for ( int i = 0 ; i < ( 1 << 10 ) ; i ++ ) { ans = Math . max ( ans , recur ( i , array , n ) ) ; } return ans ; } static public void main ( String [ ] args ) { int [ ] array = { 22 , 132 , 4 , 45 , 12 , 223 } ; int n = array . length ; System . out . println ( solve ( array , n ) ) ; } }