AV6_countSubsetWithGivenDifference.md

Count subsets with given difference

Prerequisite: Count of subset sum with given sum

sum(s1) - sum(s2) = diff
sum(s1) + sum(s2) = sum(arr)
---------------------------- ADD
2 * sum(s1) = (diff + sum(arr))
sum(s1) = (diff + sum(arr)) / 2

we have to find total number of subsets with sum -> sum(s1)

Problem is reduced to Count of subset sum with given sum.

Code

int countSubsetSum(int n, int arr[], int sum)
{
    int dp[n + 1][sum + 1];

    for (int i = 0; i < n + 1; i++)
        dp[i][0] = 1;

    for (int j = 1; j < sum + 1; j++)
        dp[0][j] = 0;

    for (int i = 1; i < n + 1; i++)
        for (int j = 1; j < sum + 1; j++)
            if (arr[i - 1] <= j)
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]];
            else
                dp[i][j] = dp[i - 1][j];

    return dp[n][sum];
}

int countSubsetDifference(int n, int arr[], int diff)
{
    int sum = accumulate(arr, arr + n, 0);
    sum = (diff + sum) / 2;
    return countSubsetSum(n, arr, sum);
}

Complexity Analysis

• Time Complexity: O(sum*n)
• Auxiliary Space: O(sum*n)

Reference

• YouTube: Count subsets with given difference

Leetcode Problem Target Sum

• Target Sum
• This problem is exact same but only problem statement is complex.
• If we add all (+) elemens and all (-) elements ans will be (+) - (-), which is Count subsets with given difference
• start 2nd inner loop from 0 instead of 1