111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455

class Solution:
    # Modulus value to avoid overflow in calculations.
    mod = int(1e9 + 7)

    def countPartitionsUtil(self, ind, target, arr):
        # Base case: If we are at the first element.
        if ind == 0:
            """ If target is 0 and element is also 0, there
            are 2 ways to achieve this (include or exclude)."""
            if target == 0 and arr[0] == 0:
                return 2
            """ If target is 0 or the element is equal to 
            target, there is 1 way to achieve this."""
            if target == 0 or target == arr[0]:
                return 1
            return 0
        
        # Calculate number of ways not including current element.
        not_taken = self.countPartitionsUtil(ind - 1, target, arr)
        
        """ Calculate the number of ways including 
        the current element (if it can be included)."""
        taken = 0
        if arr[ind] <= target:
            taken = self.countPartitionsUtil(ind - 1, target - arr[ind], arr)
        
        # Return the result 
        return (not_taken + taken) % self.mod

    def countPartitions(self, n, diff, arr):
        tot_sum = sum(arr)
        
        """If the total sum minus the difference is negative,
        or if it is not even, it's not possible to divide
        the array into two subsets with the given difference."""
        if tot_sum - diff < 0 or (tot_sum - diff) % 2 == 1:
            return 0
        
        # Calculate the target sum for one of the subsets.
        s2 = (tot_sum - diff) // 2

        """ Call the helper function to count 
        the number of subsets with sum s2."""
        return self.countPartitionsUtil(n - 1, s2, arr)

arr = [5, 2, 6, 4]
n = len(arr)
diff = 3

# Create an instance of Solution class
sol = Solution()

# Print the number of subsets found
print(f"The number of subsets found are {sol.countPartitions(n, diff, arr)}")

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869

class Solution {
    // Modulus value to avoid overflow in calculations.
    constructor() {
        this.mod = 1e9 + 7;
    }

    /* Recursive function to count the number of subsets
    with a given target sum. Uses