Write the Python Program to Find the Perfect Sum

In this tutorial, we will write the Python program to find the perfect sum from the given list. Let's understand the problem statement.

Problem Statement

Given an array arr[] of non-negative integers and an integer sum, the task is to count all subsets of the given array with a sum equal to a given sum. For example -

Example - 2:

Solution -

We can solve this problem using the recursion and dynamic programming. Let's understand the recursion approach first.

Method - 1: Using Recursion

In this approach, we will use the recursive function that will consider all subsets of the given array and check if the sum of each subset is equal to the given sum. We will use memoization to avoid repetitive calculations. Let's understand the following example.

Example -

Output:

3

Explanation -

In the above code, we define a recursive function 'count_subsets_recursive(arr, n, sum, memo) where arr is the given array, n is the number of elements in the array, sum is the target sum, and memo is a memoization table to store the intermediate results.

The base case of the recursion is when the sum is 0. In this case, we return 1, because there is always one empty subset with a sum of 0.

If the number of elements is 0 and the sum is not 0, we return 0, because there are no subsets whose sum is equal to the given sum.

For other cases, we have two choices: either we include the current element arr[n-1] in the subset or we exclude it.

If we exclude it, we call the count_subsets_recursive() function recursively for the remaining n-1 elements, so count_subsets_recursive(arr, n-1, sum, memo).

If we include it, we call the count_subsets_recursive() function recursively for the remaining n-1 elements and the remaining sum after subtracting the current element, so count_subsets_recursive(arr, n-1, sum-arr[n-1], memo).

We add the results of the above two choices and store the result in the memoization table to avoid redundant calculations. Finally, we return the result.

Method -2: Using Dynamic Programming

In this approach, we will use the dynamic programming where we define a 2D array dp[n+1][sum+1] where dp[i][j] represents the number of subset of the first i element of the array whose sum equal to j.

Let's understand the following code -

Example -

Output:

3

Explanation -

In this approach, we create a 2D array dp of size (n+1) x (sum+1), where n is the number of elements in the array and sum is the target sum. Each element dp[i][j] represents the count of all subsets of the first i elements of the array with a sum equal to j. We initialize the first column of the array to 1, because there is always one empty subset with a sum of 0. We are using the following recursion relation.

The first case represents the situation where the current element arr[i-1] is greater than the current sum j. In this case, we cannot include the current element in any subset that has a sum equal to j. Therefore, we simply copy the value of dp[i-1][j].

The second case represents the situation where the current element arr[i-1] is less than or equal to the current sum j. In this case, we can either include the current element in a subset or exclude it.

If we exclude it, the count of subsets with a sum equal to j remains the same as the count of subsets with a sum equal to j that can be formed from the first i-1 elements. If we include it, we need to find the count of subsets with a sum equal to j-arr[i-1] that can be formed from the first i-1 elements, because we have already included the current element arr[i-1].

Finally, we return the value of dp[n][sum], which represents the count of all subsets of the entire array with a sum equal to the given sum.