Home » Interview coding problems/challenges

Perfect Sum Problem

Perfect Sum Problem: Given an array of integers and a sum, the task is to count all subsets of the given array with the sum equal to the given sum.
Submitted by Divyansh Jaipuriyar, on April 10, 2021

Description: The problem has been featured in the interview/round of many top tech companies such as Amazon, Microsoft, Tesco, etc.

Problem Statement: Given an array of integers and a sum, the task is to count all subsets of a given array with the sum equal to the given sum.

Problem Description:

The problem asks you to find the number of subsets that are elements from the given array such that their sum is equal to given sum in the problem, subset size can be one if a single element is equal to a given sum or greater than one depending upon the input array.

For example: For [5,6,7,8,9] and sum = 5, the subset is {5} as a single element is equal to a given sum and for sum==12 the subset{5,7} makes it possible therefore subset size is greater than one is also possible.

Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. The next line contains n space-separated integers forming the array. The last line contains the sum.

Output: Count all the subsets of the given array with the sum equal to the given sum.

Example:

Input:	
T = 1
N = 5
[5,6,7,8,9]
Sum = 12

Output:
1

Explanation:
{7+5} = 12 therefore this is the required subset.

INPUT:
T = 1
N = 5
[1,2,3,4,0]
Sum = 5

Output:
2, {1+4} = 5 and {2+3} = 5 therefore they are the required subset.

Solution Approach:

1) Recursive Approach

We will use the recursive function solve to evaluate the count of subsets that are equal to the given sum.

We consider the following base cases:

1. if sum==0: There is an empty subset that satisfies the given case, so we return 1.
2. if n==0 and sum!=0: There is no subset that is possible to construct so return 0.
3. if(arr[n-1]>sum): Since we are checking from last to first order (n to 0) index and we are using 0 based indexing system, we can’t take this element because the value of this element is greater than the required sum so we call recursive function for rest of the element.
4. For the rest of the cases we have either we take that element or we don't take the element.
   i.e, solve(arr,n-1,sum)+solve(arr,n-1,sum-arr[n-1])

Time Complexity for the above approach is exponential.

Program to illustrate the working of recursive approach

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll solve(ll arr[], ll n, ll sum)
{
    //base condition.
    if (sum == 0)
        return 1;
    //base condition.
    else if (sum != 0 and n == 0)
        return 0;
    //if arrays element >sum.
    else if (arr[n - 1] > sum)
        return solve(arr, n - 1, sum);
    else //we have two choice either to pick or to reject.
        return solve(arr, n - 1, sum) + solve(arr, n - 1, sum - arr[n - 1]);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n;
        cout << "Enter size of array: ";
        cin >> n;

        ll arr[n];
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll sum;
        cout << "Enter sum: ";
        cin >> sum;

        ll res = solve(arr, n, sum);
        cout << "Number of subsets: ";
        cout << res << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter elements: 5 6 7 8 9
Enter sum: 12
Number of subsets: 1
Enter size of array: 4
Enter elements: 9 5 7 3
Enter sum: 10
Number of subsets: 1
Enter size of array: 6
Enter elements: 9 5 7 2 5 1
Enter sum: 23
Number of subsets: 2

Dynamic Programming Approach:

TOP-DOWN APPROACH:

Here we take dp[n][sum] as our dynamic state. Initially, we will fill the entire dp state as -1, if the dp state is calculated then its value changes so if the recursion call is made again then we first check it in the dp table whether it is calculated or not. If calculated already then simply return it, otherwise calculate it.

Follow steps are used in top-down dp:

1. We need to create some dp[][] state that will help in storing the value for some state dp[i][j] such that i is the index for an element which will be used and j is the required sum value.
2. Initially, all the dp[][] state is filled with -1 for memoization as discussed above.
3. For repeated recursive function call we would directly return from dp[i][j] state without recalculating it.
4. For new dp[i][j] state we would simply calculate according to recursion.
5. The time complexity would reduce from exponential to O(n*n).

Time complexity for above approach is O(n*n)

Space Complexity for above approach is O(n*n)

Program to illustrate the working of Top-down dynamic programming approach

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[1003][1003];

ll solve(ll arr[], ll n, ll sum)
{
    //base condition.
    if (sum == 0)
        return dp[n][sum] = 1;
    //base condition.
    else if (sum != 0 and n == 0)
        return dp[n][sum] = 0;
    //if already calculated.
    if (dp[n][sum] != -1)
        return dp[n][sum];
    //if arrays element >sum.
    else if (arr[n - 1] > sum)
        return dp[n][sum] = solve(arr, n - 1, sum);
    else //we have two choice either to pick or to reject.
        return dp[n][sum] = solve(arr, n - 1, sum) + solve(arr, n - 1, sum - arr[n - 1]);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n;
        cout << "Enter size of array: ";
        cin >> n;

        ll arr[n];
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll sum;
        cout << "Enter sum: ";
        cin >> sum;

        memset(dp, -1, sizeof(dp));
        ll res = solve(arr, n, sum);

        cout << "Number of subsets: ";
        cout << res << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 4
Enter elements: 2 3 4 5
Enter sum: 7
Number of subsets: 2
Enter size of array: 3
Enter elements: 9 8 5
Enter sum: 6
Number of subsets: 0
Enter size of array: 3
Enter elements: 9 11 12
Enter sum: 20
Number of subsets: 1

BOTTOM UP APPROACH:

In this case we will fill the dp[n][sum] state in bottom up manner. We will fill the base cases as:

1. if sum!=0 and n==0 then dp[n][sum]=0
2. if sum==0 then dp[n][sum]=1
3. else dp[i][j]=dp[i-1][j]+d[i-1][j-arr[i-1]] here we check for both cases.

Follow steps would be used in bottom-up dp:

1. Our dp[i][j] state i is the number of elements that are we using for our current sum j.
2. For all dp[i][j] where j is the sum==0, then every empty subset is possible so we make dp[i][0]=1
3. For all dp[i][j] where i==0, we can not make any subset therefore it will be 0.
4. For every other state dp[i][j] we have two cases either we include a current element or we can not include. For this case, we need our sum j need to be greater than the element present at index (i-1) 0 based index. Otherwise, we can not include it so we simply assign till previous index-based value.
5. With the help of bottom-up dp we reduced time complexity from exponential to O(n*n)

Time Complexity for above approach is O(n*n)

Space Complexity for above approach is O(n*n)

Program to illustrate the working of bottom-up dynamic programming approach

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n;
        cout << "Enter size of array: ";
        cin >> n;

        ll arr[n];
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll sum;
        cout << "Enter sum: ";
        cin >> sum;

        ll dp[n + 1][sum + 1];
        //initialise base case for sum==0
        for (ll i = 0; i <= n; i++)
            dp[i][0] = 1;

        //initialise base cases for sum!=0
        for (ll i = 1; i <= sum; i++)
            dp[0][i] = 0;
        //fill the table in bottom up manner
        for (ll i = 1; i <= n; i++) {
            for (ll j = 1; j <= sum; j++) {
                //if sum>=arr[i-1].
                if (arr[i - 1] <= j)
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]];
                else //if sum<arr[i-1].
                    dp[i][j] = dp[i - 1][j];
            }
        }

        cout << "Number of subsets: ";
        cout << dp[n][sum] << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter elements: 9 8 7 6 5
Enter sum: 4
Number of subsets: 0
Enter size of array: 5
Enter elements: 1 2 3 4 5
Enter sum: 10
Number of subsets: 3
Enter size of array: 2
Enter elements: 5 6
Enter sum: 11
Number of subsets: 1