text: Count ways to split array into pair of subsets with difference between their sum equal to K | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxN  20 NEW_LINE #define maxSum  50 NEW_LINE #define minSum  50 NEW_LINE #define base  50 NEW_LINE int dp [ maxN ] [ maxSum + minSum ] ; bool v [ maxN ] [ maxSum + minSum ] ; 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 ] = 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 ] ; } 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 ; cout << findCnt ( arr , 0 , S1 , n ) ; } int main ( ) { int arr [ ] = { 1 , 1 , 2 , 3 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int K = 1 ; countSubsets ( arr , K , N ) ; return 0 ; }