Count ways to split array into pair of subsets with difference between their sum equal to K | Python 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 ; Prthe number of subsets with sum equal to S1 ; Driver Code ; Function Call
maxN = 20 ; NEW_LINE maxSum = 50 ; NEW_LINE minSum = 50 ; NEW_LINE Base = 50 ; NEW_LINE dp = [ [ 0 for i in range ( maxSum + minSum ) ] for j in range ( maxN ) ] ; NEW_LINE v = [ [ False for i in range ( maxSum + minSum ) ] for j in range ( maxN ) ] ; NEW_LINE def findCnt ( arr , i , required_sum , n ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT if ( required_sum == 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT DEDENT if ( v [ i ] [ required_sum + Base ] ) : NEW_LINE INDENT return dp [ i ] [ required_sum + Base ] ; NEW_LINE DEDENT v [ i ] [ required_sum + Base ] = True ; NEW_LINE dp [ i ] [ required_sum + Base ] = findCnt ( arr , i + 1 , required_sum , n ) + findCnt ( arr , i + 1 , required_sum - arr [ i ] , n ) ; NEW_LINE return dp [ i ] [ required_sum + Base ] ; NEW_LINE DEDENT def countSubsets ( arr , K , n ) : NEW_LINE INDENT sum = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] ; NEW_LINE DEDENT S1 = ( sum + K ) // 2 ; NEW_LINE print ( findCnt ( arr , 0 , S1 , n ) ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 1 , 2 , 3 ] ; NEW_LINE N = len ( arr ) ; NEW_LINE K = 1 ; NEW_LINE countSubsets ( arr , K , N ) ; NEW_LINE DEDENT