Check if an array can be split into 3 subsequences of equal sum or not | Java program for the above approach ; Function to check array can be partition into sum of 3 equal ; Base Case ; If value at particular index is not - 1 then return value at that index which ensure no more further calls ; When element at index j is added to sm1 ; When element at index j is added to sm2 ; When element at index j is added to sm3 ; Update the current state and return that value ; Function to check array can be partition to 3 subsequences of equal sum or not ; Initialise 3 sums to 0 ; Function Call ; Driver Code ; Given array arr [ ] ; Function Call
import java . util . * ; class GFG { static HashMap < String , Integer > dp = new HashMap < String , Integer > ( ) ; static int checkEqualSumUtil ( int arr [ ] , int N , int sm1 , int sm2 , int sm3 , int j ) { String s = String . valueOf ( sm1 ) + " _ " + String . valueOf ( sm2 ) + String . valueOf ( j ) ; if ( j == N ) { if ( sm1 == sm2 && sm2 == sm3 ) return 1 ; else return 0 ; } if ( dp . containsKey ( s ) ) return dp . get ( s ) ; else { int l = checkEqualSumUtil ( arr , N , sm1 + arr [ j ] , sm2 , sm3 , j + 1 ) ; int m = checkEqualSumUtil ( arr , N , sm1 , sm2 + arr [ j ] , sm3 , j + 1 ) ; int r = checkEqualSumUtil ( arr , N , sm1 , sm2 , sm3 + arr [ j ] , j + 1 ) ; dp . put ( s , Math . max ( Math . max ( l , m ) , r ) ) ; return dp . get ( s ) ; } } static void checkEqualSum ( int arr [ ] , int N ) { int sum1 , sum2 , sum3 ; sum1 = sum2 = sum3 = 0 ; if ( checkEqualSumUtil ( arr , N , sum1 , sum2 , sum3 , 0 ) == 1 ) { System . out . print ( " Yes " ) ; } else { System . out . print ( " No " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 17 , 34 , 59 , 23 , 17 , 67 , 57 , 2 , 18 , 59 , 1 } ; int N = arr . length ; checkEqualSum ( arr , N ) ; } }