Count ways to split array into pair of subsets with difference between their sum equal to K | Javascript 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
var maxN = 20 ; var maxSum = 50 ; var minSum = 50 ; var base = 50 ; var dp = Array . from ( Array ( maxN ) , ( ) => Array ( maxSum + minSum ) ) ; var v = Array . from ( Array ( maxN ) , ( ) => Array ( maxSum + minSum ) ) ; function findCnt ( arr , i , required_sum , 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 ] = 1 ; 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 ] ; } function countSubsets ( arr , K , n ) { var sum = 0 ; for ( var i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } var S1 = ( sum + K ) / 2 ; document . write ( findCnt ( arr , 0 , S1 , n ) ) ; } var arr = [ 1 , 1 , 2 , 3 ] ; var N = arr . length ; var K = 1 ; countSubsets ( arr , K , N ) ;