Count of all subsets with given sum in an unsorted integer array

Given an array of unsorted integers of size ‘N,’ we aim to find all subsets count with sum is equivalent to a given sum.

array = { 1, 2, 3, 4 } and sum = 6
subsets with sum 6 are {1, 2, 3}, {2, 4}
So, the count of subsets here is 2.

A subset array is an array in which all the items on it exists in another bigger array. Here the array is called subset to the larger array.

For example for the above array {1, 2, 3, 4} sub arrays are:
{1},
{2}, 
{3}, 
{4}, 
{1,2}, 
{1,3}, 
{1,4}, 
{2, 3}, 
{2, 4}, 
{3, 4}, 
{1, 2, 3}, 
{1, 2, 4}, 
{1, 3, 4}, 
{2, 3, 4}, 
{1, 2, 3, 4}

To find the count of all subarrays which sums up the given input, either we can use recursion or dynamic programming.

1. Recursion approach
2. Dynamic Programming

Recursion

Before we start finding the recursion formula, we need to understand the recursive way. Let’s take if we have ‘N’ items in the array in, and we need to find the count of subarrays that sums up to ‘K.’

First of all, we pick either the first or last item in the array. Whatever we chose might be in the resultant subset or might not be in the subarray. So, if the ‘Nth’ item in the subgroup picks, then we have to make a sum “K-N” with the remaining subset. If it is not selected, then we have to make a sum “K” with a subset except ‘Nth’ item.

Let’s formulate this recursion analogy

F(A, N, K) = 0    // if N < 0 or K < 0
           = 1    // if N is -1 and K is 0
           = F(A, N-1, K-A[N]) + F(A, N-1, K)    // otherwise, form subset with Nth item and don't form with Nth item.

Let’s write the complete code for this recursive approach.

int countSubsetSumEqualsGivenSumRec(int arr[], int size, int sum)
{
    if (sum < 0 || size < -1)
    {
        return 0;
    }
    else if (size == -1 && sum == 0)
    {
        return 1;
    }

    return countSubsetSumEqualsGivenSumRec(arr, size - 1, sum) +
           countSubsetSumEqualsGivenSumRec(arr, size - 1, sum - arr[size]);
}

Complexity of this recursive approach is where ‘N’ is size of array.

Dynamic Programming approach

To overcome the recursive approach exponential running time problem, we have a dynamic programming approach in which we can solve this problem in runtime, which is far more better than recursive runtime.

	0	1	2	3	4	5	6
1	1	1	0	0	0	0	0
2	1	1	1	1	0	0	0
3	1	1	1	2	1	1	1
4	1	1	1	1	2	2	2

The dynamic programming approach formula is similar to the recursion formula, which is as follows.

dp[i][j]    = 0    // if i=0 and j != arr[i]
            = 1    // if j=0 or (i=0 and j=arr[i])
            = dp[i-1][j]    // if j < arr[i]
            = dp[i-1][j] + dp[i-1][j-arr[i]]

Let’s write the code for this dynamic programming approach based on the above formula.

int countSubsetsWithGivenSumDP(int arr[], int size, int sum)
{
    int dp[size][sum + 1];
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j <= sum; j++)
        {
            if (i == 0)
            {
                if (j == arr[i])
                {
                    dp[i][j] = 1;
                }
                else
                    dp[i][j] = 0;
            }
            if (j == 0)
            {
                dp[i][j] = 1;
            }
            else if (i > 0)
            {
                if (j < arr[i])
                {
                    dp[i][j] = dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]];
                }
            }
        }
    }
    return dp[size - 1][sum];
}

As we already discussed, the complexity of this algorithm is where N is array size, and K is the sum to form with subsets. The complete code with the main function is as follows.

// Output
Count subsets sum using Recursion: 2
Count subsets sum using Dynamic Programming: 2

It is all about counting the number of subsets of the array, which sums up to a given sum. If you know any better performing approach, please let our readers know by commenting here below. Happy Learning!.

See more:

Find a subset of the given array with a given sum

Find the maximum subarray sum in an unsorted integer array