Count ways to split array into pair of subsets with difference between their sum equal to K | Java program for the above approach ; To store the states of DP ; Function to find count of subsets with a given sum ; Base case ; If an already computed subproblem occurs ; Set the state as solved ; Recurrence relation ; Function to count ways to split array into pair of subsets with difference K ; Store the total sum of element of the array ; Traverse the array ; Calculate sum of array elements ; Store the required sum ; Print the number of subsets with sum equal to S1 ; Driver Code ; Function Call
import java . io . * ; import java . util . * ; class GFG { static int maxN = 20 ; static int maxSum = 50 ; static int minSum = 50 ; static int Base = 50 ; static int [ ] [ ] dp = new int [ maxN ] [ maxSum + minSum ] ; static boolean [ ] [ ] v = new boolean [ maxN ] [ maxSum + minSum ] ; static int findCnt ( int [ ] arr , int i , int required_sum , int n ) { if ( i == n ) { if ( required_sum == 0 ) return 1 ; else return 0 ; } if ( v [ i ] [ required_sum + Base ] ) return dp [ i ] [ required_sum + Base ] ; v [ i ] [ required_sum + Base ] = true ; dp [ i ] [ required_sum + Base ] = findCnt ( arr , i + 1 , required_sum , n ) + findCnt ( arr , i + 1 , required_sum - arr [ i ] , n ) ; return dp [ i ] [ required_sum + Base ] ; } static void countSubsets ( int [ ] arr , int K , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } int S1 = ( sum + K ) / 2 ; System . out . print ( findCnt ( arr , 0 , S1 , n ) ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 1 , 2 , 3 } ; int N = arr . length ; int K = 1 ; countSubsets ( arr , K , N ) ; } }