Be yourself; everyone else is already taken.
Oscar Wilde
Print All Paths With Target Sum Subset
Welcome back dear reader
So, how is it going with the dynamic programming problems? We hope
that you are enjoying yourself a lot and learning even more. So, let us discuss this problem
called " PRINT ALL PATHS WITH TARGET SUM SUBSET."
So, what does this problem say? We hope that you
have solved the
SUM SUBSET PROBLEM in the foundation course. So, do you remember that
problem? We used to have an array with an input target and we used to print true if any subset
inside the array existed with the sum of all the elements equal to the target. Have a look at
the image given below:
So, if you remember we used to print true if we have even one subset with the target sum and we
used to print false if there isn't any subset with the target sum. (We have written the subsets
whose sum is equal to the target sum just for the explanation purpose. We did not print any
subsets in that problem.)
Now, we have an extended version of the same problem. We have to not just print true or false but
we also have to print all the paths in the array by which we get the target sum subset. Have a
look at the image below:
The above image shows the expected output for the given input. We will first print true that
there is some subset with the target sum inside the array. Next, we printed "2 4 ". These are
the indices of the array whose elements summed together equal the target sum subset. The element
at index 2 is 7 and at index 4 is 3, so the sum is 10. Similarly, the elements at indexes 1,2,
and 3 are 2,7 and 1 which sum up to 10. The same is the case with the third output.
So, dear reader, we hope that you have understood the question completely. We request you refer
to thePRINT ALL PATHS WITH TARGET SUM SUBSET VIDEO to understand the problem
completely and clear your doubts regarding the problem if any.
Problem Explanation:
Let us begin with the first part of the problem. This is the same as the
SUM SUBSET
PROBLEM in the foundation course. We recommend you refer to the TARGET SUM SUBSET
SOLUTION
VIDEO
to understand the first part of the article and the first part of this question completely
as we
are going to have a quick look at the procedure only as we have already studied the first
part.
Let us start applying the dynamic programming procedure step by step.
Storage and Meaning:
We will make a 2-d matrix dp of size (n+1) x (t+1) where n is the number of elements in the input
array and t is the target. For instance, if the input array is arr[5]={4,2,7,1,3}, and the
target is 10, the matrix will look like this:
As you can see, we have kept the targets from 0 to t (both including, here t is our input target)
on the columns of the matrix and the input elements of the array at the rows of the 2-D matrix.
The small numbers at the subscript of these elements indicate their positions (indexes) in the
input array. For instance, 40 indicates that element 4 is present at index 0 in the input array
whereas it is on the 1st row in the dp matrix.
The small cross at the first row indicates an empty set. This is taken because an empty array is
a subset of every set (this is the basic set theory).
Now, let us try to find out what each cell/element in this dp matrix represents. Have a look at
the image shown below:
The above image gives an example of what a cell at row=3 and column=5 represents. Similarly, any
element in the matrix will represent whether the array till there (till the element at the
current row) contains the target sum (given by the current column number) or not.
So, we have understood the storage and meaning now. Let us move to the direction of solving and
fill some initial values in this dp matrix.
Direction of Solving:
Let us now identify the direction of solving. If we have a look at image-4, we will get an idea
of what each cell represents. So, if we think carefully, the 0th (denoted by a cross) is for the
empty array (or set). The empty set will have only one subset and that is the empty set itself.
This means we have only one empty array. So, what can be the sum of the elements of this array?
Yes, it will be 0 only as there are no elements in the array.
So, the 0th row which represents the empty array can have only one sum, and i.e. 0 and all the
other sums cannot be found in the subset of the empty set. So, the first element is the 0th row
will be true and the rest all will be false.
So, the first row represents that the empty array will have a subset that can produce sum=0 and
it does not have any subset which produces any other sum. (The ticks in the diagram correspond
to the true values and the crosses correspond to the false values)
Now, let us fill the 0th column. See, every array has an empty set (array) as its subset. So,
every array has a subset that produces a sum of 0. So, all the values in the 0th column will be
true as every array will have a subset that produces sum=0.
So, what is the small problem? The smallest problem is the cell at 0th row and 0th column as it
tells whether an empty set has a subset that produces sum 0 or not.
Since we have already found the answers for the 0th row and the 0th column, they are small
problems and hence the direction of solving will be from dp[0][0] to dp[n][t]. Now let us move to the final step of traveling the matrix and solving to get an answer.
Travel and Solve:
So, we have already filled the 0th row and the 0th column. So, let us start from row=1 which
represents the array {4}. So, when we have only one element in the array, there are only two
possible subsets. One is the array itself and the other is the empty array. The empty array can
produce sum=0, which we have already considered in the 0th column. So, we are left with only one
subset and that is the array itself. So, the sum of elements in this array is 4 i.e. the only
element present in this array. So, the subsets of this array can only produce 2 sums, 0 and 4.
So, we will put true in dp[1][4] and false in all the other cells of the first row (except
dp[1][0] which is already true).
Now, let us try to fill the 2nd row. We are initially at dp[2][1]. This means that we have to
check whether the array {4,2} has a subset that has a sum=1. The subsets of this array will be
{4}, {2} ,{4,2} and {}. This means that no subset will have a sum of 1. So, we will put false
here.
When we are at dp[2][2], the subset {2} will have a sum of 2. So, we will put true here.
Now, when we are at dp[2][3] and the element that we are focusing on is 2. So, will the subset
{2} be able to complete the sum 3? The answer is no, it will not. So, it cannot complete 3 alone
but what if the elements in the array till here before 2 added with this element 2 could
complete it?
So, we will assume that 2 is selected. So, the remaining sum is 1. We will now check whether the
array before including 2 was able to get a sum of 1 or not. So, we go at dp[1][1] and here we
have a value of false. This means that if we include 2, we will not be able to make the sum and
since 2 is not equal to the target sum itself, it is also not sufficient to produce the required
sum. So, 2 itself or with the previous subsets, cannot produce the sum 3 and we will put false
at dp[2][3].
The same will happen for 4 and 5.
Now, we reach dp[2][6]. So, if we include 2, it is smaller than the target sum 6 and will not be
able to complete the target sum itself. So, let us check whether it will be able to complete the
target sum when we consider the previous elements. So, if we include 2, the remaining sum is 4.
Now, the elements before 2 must have a subset that produces a sum of 4. So, we go at dp[1][4]
and it is true. This means that the sum can be completed if 2 is included with the previous
subset. So, the array {4,2} has a subset that can produce a sum of 6, and hence we will put true
here.
The further values in this row will be false. Why? Think!!
So, dear reader, you can fill the entire matrix in this way ad the matrix will finally look like
this:
So, dear reader, we hope that you have understood the above procedure. This might have been easy
for you as you have already studied this procedure. Still, if you have any doubts regarding this
procedure, refer to the solution video to understand the complete procedure
explained above.
So, this procedure was just about printing true if any subset with the target sum exists and
printing false if it doesn't. Now, let us move to the next part of the question i.e. printing
the paths from where we get our answers.
Let us Analyze:
Have a look at the matrix that we have filled up (img-10). Let us start from the last element of
the matrix. So, if we would have taken element 3 in our subset, the remaining sum would be 7 and
the remaining array (before 3) was able to produce 7 as well. If we do not take 3, then the
complete target sum 10 is remaining and the array before element 3 was having the subsets which
could produce the target sum of 10.
So, in a way, we can say that there is one call for "no" i.e. 3 will not be selected into the
subset and the sum, in this case, remains 10 and since we reach a true in the matrix after this
call, this means that the sum=10 can be generated without taking 3 as well.
There is also a "yes" call i.e. 3 is selected into the subset and the remaining sum is 7. Since
we again reach a true in the matrix, this means that the remaining array is able to
produce the remaining sum.
Now, let us continue this procedure from the cells that we have arrived at into the matrix. So,
let us continue for the initial "no" call i.e. we are at dp[4][10].
So, when element 1 is taken into the subset, the remaining sum is 9 and since we reach a
true
there too, the recursion will continue there as well. On the other hand, when we do not select
one as well, we reach a false i.e. the call will be terminated here and we will not apply
the
procedure after this (the cell highlighted in yellow).
Let us continue the call from dp[3][9] i.e. when 3 was not selected and 1 was selected and the
remaining sum is 9.
So, when 7 is not selected, the remaining sum is still 9 and the array before 7 i.e. {4,2} cannot
produce any subset with sum 9. So, we reach a false and the call will be terminated from
here.
On the other hand, when 7 is selected, the remaining sum is 2 and we reach true i.e. the
array
{4,2} has a subset that has a sum of 2.
Let us continue from dp[2][2]. Here, if 2 is selected into the subset then the remaining sum is
zero and the remaining array i.e. {4} has a subset that has a sum of 0 (and that is????). On the
other hand, we will reach a false if 2 is not selected as the remaining array {4} does not have
any subset whose sum is 2. So, the call will be terminated here.
Now, element 4 does not have an option to get selected as the target sum is 0. So, there is only
one possibility that 4 should not be selected. So, if it is not selected, we reach a true
as the remaining sum is 0 and the empty array has a subset that has a sum 0.
So, dear reader, we hope that you have understood what we are doing here. We recommend you trace
the remaining path by yourself. The matrix will look like this:
We know that this is a bit confusing. Hence, we recommend you refer to the solution video to
understand the above procedure completely.
So, if you trace the 3 paths that are reaching dp[0][0] starting from dp[n][target], you will see
that these three paths will give the yes calls for the elements whose sum will be 10 i.e. the
target sum. Now the question that arises is how we are going to implement this in the code?
How will we implement this?
So, this was quite a tricky procedure that we did up there, huh? Now, we will see how we can
implement this procedure in terms of the java code.
We will use a queue to implement this procedure. We will first add the last element of the dp to
the queue. Now, we will dequeue it from the queue and see for both its "yes" and "no" calls.
Wherever the value is true, we will put that value into the queue and continue till we reach
dp[0][0].
If you want to understand this procedure with an example, refer to the solution video to
understand it well.
So, dear reader, we hope that you have understood the complete procedure and enjoyed learning
this question. Now that we have discussed everything regarding the procedure, let us write the
code quickly.
Java Code
import java.io.*;
import java.util.*;
public class Main {
public static class Pair{
int i;
int j;
String psf;
public Pair(int i, int j, String psf){
this.i = i;
this.j = j;
this.psf = psf;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) { arr[i]=Integer.parseInt(br.readLine()); } int
tar=Integer.parseInt(br.readLine()); boolean[][] dp=new boolean[arr.length + 1][tar + 1]; for
(int i=0; i < dp.length; i++) { for (int j=0; j < dp[0].length; j++) { if (i==0 && j==0) {
dp[i][j]=true; } else if (i==0) { dp[i][j]=false; } else if (j==0) { dp[i][j]=true; } else {
if(dp[i - 1][j]==true){ dp[i][j]=true; } else { int val=arr[i - 1]; if (j>= val && dp[i - 1][j -
val] == true) {
dp[i][j] = true;
}
}
}
}
}
System.out.println(dp[dp.length - 1][tar]);
Queue< Pair> q = new ArrayDeque<>();
q.add(new Pair(n,tar,""));
while (q.size() > 0) {
Pair rp = q.remove();
if (rp.i == 0 || rp.j == 0) {
System.out.println(rp.psf);
} else {
boolean exc = dp[rp.i - 1][rp.j];
boolean inc = rp.j - arr[rp.i - 1] >= 0 ? dp[rp.i - 1][rp.j - arr[rp.i - 1]] : false;
if (inc == true) {
q.add(new Pair(rp.i - 1, rp.j - arr[rp.i - 1], (rp.i - 1) + " " + rp.psf));
}
if (exc == true) {
q.add(new Pair(rp.i - 1, rp.j, rp.psf));
}
}
}
}
}
java;
true";
So, dear reader, we hope that you have got the code too. The above code is written and explained in
the solution video (25:32 onwards). We recommend you refer to it at least once. This will help
strengthen your concepts a lot. So, we have discussed everything now. Let us discuss the time and
space complexity analysis.
Time and Space Complexity Analysis
Time Complexity: The time complexity of the above solution will be O(target x n) as we
are
traversing a matrix of size (target+1) x (n+1) where the target is the target sum given to us
and n is the length of the given array. Why are we not considering the time taken by the queue?
Are we not considering it or we have considered it? Think about these things!!!
Space Complexity: The space complexity is also O(target x n) because we made a matrix of
size
(target+1) x (n+1). Again, why are we not considering the space taken by the queue, or we have
already considered it while calculating the space complexity? Think about this!!
So, dear reader, we hope that you have understood the problem completely. If you still have any
doubts regarding this, refer to the complete solution video to understand the solution
completely. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
You must have solved the TARGET
SUM SUBSET PROBLEM in the foundation course before moving on with this problem as more
than half
of the problem is the same.
You must also have a good knowledge of Breadth-First Search of graphs for understanding the last
procedure that we did with the queue.
So, you must have completed and revised the foundation course at least once as these problems
are all
based on a lot of previous knowledge and you will face difficulty if you directly jump to these
problems. Hence we recommend you to once revise these topics in the foundation course if you
have
already studied them otherwise first study the foundation course completely. Till then Happy
Coding!!!
