Dynamic Programming: Count the number of subset with a given difference

Problem Statement:

You are given with an array and a difference.

You need to count the number of subsets with a given difference.

Example

Input: {1, 1, 2, 3}
Diff = 3

Output = 2

{1, 1} {2, 3}
{1, 1, 3} {2}

Solution

This problem is similar to 0/1 knapsack problem.
i.e for every element we have a choice to choose the element in set 1 or in set 2.

So we know that s1 + s2 = total array sum “S”.

s2 = S – s1

Now we need to get the number of ways to divide the array into 2 subsets that matches the given difference.

s1 – s2 = diff

s1 – (sum – s1) = diff

s1 = (diff+sum)/2

So now we need to get the number of subsets with sum = s1.

This is subset sum problem.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int dp[20001][20001];


int countSubsets(int arr[], int n, int sum)
{
  if (dp[n][sum] != -1)
    return dp[n][sum];
  // base case
  if (sum == 0)
    return 1;
  if (n == 0)
    return 0;
  if (arr[n - 1] <= sum)
    return dp[n][sum] = countSubsets(arr, n - 1, sum - arr[n - 1]) + countSubsets(arr, n - 1, sum);
    
  return dp[n][sum] = countSubsets(arr, n - 1, sum);
}

int count_subsets_diff(int arr[], int n, int diff)
{
  int arr_sum = 0;
  // sum of the array
  for (int i = 0; i < n; i++)
    arr_sum += arr[i];

  int sum = (diff + arr_sum) / 2;
  
  return countSubsets(arr, n, sum);
}


int main()
{
    memset(dp, -1, sizeof(dp));
    int S[] = { 1, 1, 2, 3};
    int n = sizeof(S) / sizeof(S[0]);
    int diff = 3;
 
    cout << "The subsets with the given difference is " << count_subsets_diff(S, n - 1, diff)<<endl;
 
    return 0;
}

Output:

The subsets with the given difference is 2