Problem Description

Given an array arr[] of length N of positive integers and an integer X, the task is to find the pairs of subsets S1 and S2 such that S1 + S2 = S and abs(S1 - S2) = X

Problem Link

https://www.youtube.com/watch?v=ot_XBHyqpFc&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=11&ab_channel=AdityaVerma

Approach

The given problem is similar to Count of subsets with sum equal to a given value

sum1 + sum2 = totalSum and,

sum1 - sum2 = X

So from above two equations we found that

sum1 = (totalSum + X)/2

Thus we have to simply find the no. of subsets having given sum as (totalSum + X)/2.

int findSubsets(vector<int>& nums, int diff) {
       
        int n = nums.size();
        int sum = 0; //totalSum
        
				for(int ele:nums)
          sum+=ele;
        //if all the array elements are positive then sum of the two subsets has to be
        //greater than the difference between them    
        //if sum+diff%2==1 which means that our newSum will not be an integer.
        if (sum<diff||(sum + diff) % 2 == 1) return 0;
            
        int newSum = (sum+diff)/2;
        
        int dp[n+1][newSum+1];
        
        dp[0][0] = 1;
        
        for (int i = 1; i <= newSum; i++)
        dp[0][i] = 0;
        
        for (int i = 1; i <= n; i++)
        dp[i][0] = 1;
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=newSum;j++)
            {
               //excluding if the number if it is gretaer than the current sum j   
               if(j<nums[i-1])
                    dp[i][j] = dp[i-1][j];
               else
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                
                
                    
            }
        }
        
        return dp[n][newSum]; 
        
    }