Target Sum
Application of 0/1 Knapsack Concept

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
You are given a list of nonnegative 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
+11+1+1+1 = 3
+1+11+1+1 = 3
+1+1+11+1 = 3
+1+1+1+11 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Solution:
Prerequisites for this problem are:
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_{1}, I_{2} and I_{3}
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 nonnegative, 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 TakeAways:
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 wellrounded software engineer knows how important it is to have the skill of not reinventing 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:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.