Saturday, December 3, 2022
HomeSoftware DevelopmentDepend of Subsets with given Distinction

Depend of Subsets with given Distinction


Given an array arr[] of measurement N and a given distinction diff, the duty is to depend the variety of partitions that we are able to carry out such that the distinction between the sum of the 2 subsets is the same as the given distinction.

Observe: A partition within the array means dividing an array into two elements say S1 and S2 such that the union of S1 and S2 is the same as the unique array and every ingredient is current in solely of the subsets.

Examples:

Enter: N = 4, arr[] = [5, 2, 6, 4], diff = 3
Output: 1
Clarification: We will solely have a single partition which is proven beneath:
{5, 2} and {6, 4} such that S1 = 7 and S2 = 10 and thus the distinction is 3

Enter: N = 5, arr[] = [1, 2, 3, 1, 2], diff = 1
Output: 5
Clarification: We will have 5 partitions which is proven beneath
{1, 3, 1} and {2, 2} – S1 = 5, S2 = 4
{1, 2, 2} and {1, 3} – S1 = 5, S2 = 4
{3, 2} and {1, 1, 2} – S1 = 5, S2 = 4
{1, 2, 2} and {1, 3} – S1 = 5, S2 = 4
{3, 2} and {1, 1, 2} – S1 = 5, S2 = 4

 

Naive Strategy: The issue might be solved primarily based on the next mathematical thought:

  • Suppose the array is partiotioned in two subsets with sum S1 and S2, so we all know that,  
    • S1 + S2  is the overall sum array nums 
    • S1 – S2 is the given diff
  • Subtracting the 2 equations we might get,
    • sum – diff = (S1 + S2) – (S1 – S2) = 2*S2 . So, S2 = ( sum – diff ) / 2
    • From this we get the concept a component X might be partiotioned in just one approach when the distinction between the 2 partitions is given. 
    • Due to this fact, on this case of array the overall variety of doable methods will depend on the variety of doable methods to create a subset having sum S2. 

So we are able to use the idea of recursion to generate all doable subsets with sum S2. For every ingredient there are two decisions: both be part of the subset S2 or not.

Within the above thought, there are situations seen that should be glad for the subset to exist:

  • The distinction between array sum and diff should be a optimistic quantity and
  • This worth should be a good quantity (As this is identical as 2*S2).

Time Complexity: O(2N)
Auxiliary House: O(N)

Environment friendly Strategy: The concept is analogous because the naive one. However right here we are going to use the concept of dynamic programming to optimize the time complexity.

Upon shut statement, it may be seen that any state might be uniquely outlined unsing two parameters, one parameter represents the index, and the opposite one represents the sum (S2) of the subset shaped utilizing components from the beginning until that index.

So, we are able to depend the variety of methods to kind the subset from every state and may reuse them to keep away from repeated calculations.

Comply with the steps talked about beneath to implement the strategy:

  • Calculate the sum of  the array.
  • Create a 2 dimensional array dp[][] with dimension (N * array sum) to retailer the calculated worth of every state.
  • Traverse the array utilizing recursion and generate two calls.
    • If the worth for the state is already calculated, reuse the worth.
    • In any other case there are two instances:
      • If including the present ingredient won’t make the currentSum greater than S2, then generate two calls, one with the present ingredient added to the currentSum and the opposite with out including it.
      • If including the present ingredient will increase currentSum above S2, then we solely generate one name with out including the present ingredient.
    • If the currentSum is the same as S2 then we return 1.
  • Return the ultimate worth obtained on this approach as the reply.

Beneath is the implementation of the above strategy.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

int dp[1001][10000];

  

int countSubsets(vector<int>& v, int i, int S2,

                 int currentSum)

{

    if (currentSum == S2) {

        return 1;

    }

    if (i >= v.measurement()) {

        return 0;

    }

    if (dp[i][currentSum] != -1) {

        return dp[i][currentSum];

    }

    if (currentSum + v[i] > S2) {

        return dp[i][currentSum]

               = countSubsets(v, i + 1, S2, currentSum);

    }

    else {

        return dp[i][currentSum]

               = countSubsets(v, i + 1, S2,

                              currentSum + v[i])

                 + countSubsets(v, i + 1, S2, currentSum);

    }

}

int countSub(vector<int>& vp, int N, int diff)

{

    int sum = 0;

    for (auto& worth : vp)

        sum += worth;

    

    if (sum - diff < 0 || (sum - diff) % 2 == 1) {

        return 0;

    }

    

    

    

    

    return countSubsets(vp, 0, (sum - diff) / 2, 0);

}

  

int foremost()

{

    int N = 5;

    vector<int> arr = { 1, 2, 3, 1, 2 };

    int diff = 1;

    memset(dp, -1, sizeof(dp));

  

    

    cout << countSub(arr, N, diff) << endl;

    return 0;

}

Time Complexity: O(N*(sum of the subset))
Auxiliary House: O(N * array sum)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments