🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.

Solution:

Pre-requisites for this problem are:

• 0/1 Knapsack Problem
• Subset Sum Problem
• Minimum Subset Sum Difference

In this problem, we are required to include each and every item and assign either + or - sign to them, in a way that they all sum up to the target. So if we have 3 items I₁, I₂ and I₃ we would have something like below:

     I1         I2        I3
    /  \       /  \      /  \
   -    +     -    +    -    +

So this is very similar to 0/1 Knapsack Problem. In 0/1 Knapsack Problem you can assign 0 or 1 to every item where 0 would mean that item is NOT getting included and 1 would mean that you include the item. Think of as if you are to put exactly target amount of weight in the knapsack.

Lets say the sum of all the items which are assigned + is S1 and sum of all the items which are assigned - is S2 where S1 >= 0 and S2 > 0. Important to notice that I am saying that the sum of all the items which are assigned - sign is S2 and not -S2 that is because all the given numbers are non-negative, so their sum is a positive number as all. The sum for - assigned numbers will become negative only when we take the - sign into consideration and this this is what we would get:

S1 - S2 = Target
or, S1 - (sum - S1) = Target
or, 2S1 - sum = Target
sum = sum of all given numbers
So, sum = S1 + S2

S1 is sum of one subset of the nums[] array and S2 is sum of the remaining items (not -S2 because the negative numbers are not part of the original array. We convert them to negative by assigning - sign. Originally they would sum up to S2, and then since they have gotten - sign assigned, their sum S2 also gets - sign assigned since summation of negative numbers is a negative number).

So the problem now becomes finding in how many ways the given numbers can be divided in two subsets such the difference between the sum of the two subsets is equal to Target. This is commonly known as Subset Sum Difference Problem. A very similar problem is Minimum Subset Sum Difference, and I would highly recommend going though that problem first.

Algorithm:

If a subset has sum i then the sum of the remaining integers would be (sum of all given integers) - i. We are interested in finding count of cases where Math.abs(i - (sum of remaining integers)) = Target.

Let dp[i] = number of unique subsets that sum up to i for all i = 0 to (sum of all given integers). Then the count of i's for which (sum of all given integers) - i = target will give us the answer.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Yet Another Solution with Even More Observations:

Let's take a deeper look at the equation we had in our last solution:

S1 - S2 = Target
or, S1 - (sum - S1) = Target
or, 2S1 - sum = Target
or, S1 = (Target + sum) / 2

So the problem now reduces to finding how many subsets are there with subset sum = (Target + sum) / 2

Edge case:
2 * S1 = Target + Sum
From above equation we see that (Target + Sum) is an even number.
If (Target + Sum) is odd then the above equation does not hold.
So, and edge case is if (Target + Sum) % 2 != 0 then there is NO such subset that satisfies the condition we are looking for.

We have already discussed Subset Sum Problem in one of our prior chapters, so the below code should look familiar.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Key Take-Aways:

This problem is a perfect example of how knowing the classic algorithm problems and having a strong understanding of foundational algorithm concepts can help you nail even the seemingly difficult problems quite easily. This problem is also a great example of how so many different problems can be reduced to classic algorithm problems and being able to reuse our learning of the foundational concepts is the key. See how beautifully we have reused the solutions of prior known problems and designed algorithm for this problem based off of them. An experienced well-rounded software engineer knows how important it is to have the skill of not re-inventing the wheel and reusing other extensible software components whenever possible. My goal is not only to make you great in designing algorithms but also to make you a well versed engineer who knows the best practices and writes code and builds components that he/she would be humbly proud of and would succeed in his/her professional life.

For this problem our building blocks were: Foundational Knowledge and Deep Understanding of 0/1 Knapsack, Subset Sum Problem, and Minimum Subset Sum Difference.

The second solution demonstrate how keeping an open mind and leveraging knowledge of simple high school mathematics can often simplify seemingly complicated problems.

Instructor: