22XX402 – DATA STRUCTURES II

UNIT IV & LP 13 – NP COMPLETE PROBLEMS,

BACKTRACKING: N-QUEENS PROBLEM AND SUBSET-
SUM PROBLEM

1. NP COMPLETE PROBLEMS:
The computing times of algorithms fall into two groups.

● Group1– consists of problems whose solutions are bounded by the polynomial of

small degree.
Example – Binary search o (log n) , sorting o(n log n), matrix multiplication 0(n
2.81).

● Group2 – contains problems whose best known algorithms are non polynomial.

Example –Traveling salesperson problem 0(n22n), knapsack problem 0(2n/2) etc.

1.1 NP –HARD AND NP – COMPLETE PROBLEMS

There are two classes of non polynomial time problems
1. NP- hard
2. NP-complete
A problem which is NP complete will have the property that it can be solved in polynomial
time iff all other NP – complete problems can also be solved in polynomial time.
The class NP (meaning non-deterministic polynomial time) is the set of problems that
might appear in a puzzle magazine: ``Nice puzzle.'' What makes these problems special is
that they might be hard to solve, but a short answer can always be printed in the back, and
it is easy to see that the answer is correct once you see it.
Example... Does matrix A have LU decomposition?
No guarantee if answer is ``no''.
Another way of thinking of NP is it is the set of problems that can solved efficiently by a
really good guesser. The guesser essentially picks the accepting certificate out of the air
(Non-deterministic Polynomial time). It can then convince itself that it is correct using a
polynomial time algorithm. (Like a right-brain, left-brain sort of thing.) Clearly this isn't a
practically useful characterization: how could we build such a machine?

● Exponential Upper bound

Another useful property of the class NP is that all NP problems can be solved in
exponential time (EXP). This is because we can always list out all short certificates in
exponential time and check all O (2nk) of them. Thus, P is in NP, and NP is in EXP.
Although we know that P is not equal to EXP, it is possible that NP = P, or EXP, or
neither. Frustrating!

● NP-hardness

As we will see, some problems are at least as hard to solve as any problem in NP.
We call such problems NP-hard. How might we argue that problem X is at least as
hard (to within a polynomial factor) as problem Y? If X is at least as hard as Y, how
would we expect an algorithm that is able to solve X to behave?
1.1.1 NP –HARD and NP – Complete Problems Basic Concepts
If an NP-hard problem can be solved in polynomial time, then all NP-complete
problems can be solved in polynomial time.
All NP-complete problems are NP-hard, but all NP- hard problems are not NP-complete.
The class of NP-hard problems is very rich in the sense that it contains many problems
from a wide variety of disciplines.

● P: The class of problems which can be solved by a deterministic polynomial

algorithm.

● NP: The class of decision problem which can be solved by a non-deterministic

polynomial algorithm.

● NP-hard: The class of problems to which every NP problem reduces

● NP-complete (NPC): the class of problems which are NP-hard and belong to NP.

1.1.2 NP-Competence
• How we would you define NP-Complete
• They are the “hardest” problems in NP
NP-complete problems are a subset of the larger class of NP (nondeterministic
polynomial time) problems. NP problems are a class of computational problems that can be
solved in polynomial time by a non-deterministic machine and can be verified in
polynomial time by a deterministic Machine. A problem L in NP is NP-complete if all
other problems in NP can be reduced to L in polynomial time. If any NP-complete problem
can be solved in polynomial time, then every problem in NP can be solved in polynomial
time. NP-complete problems are the hardest problems in the NP set.

A decision problem L is NP-complete if it follow the below two properties:

● L is in NP (Any solution to NP-complete problems can be checked quickly, but no

efficient solution is known).

● Every problem in NP is reducible to L in polynomial time (Reduction is defined

below).

● A problem is NP-Hard if it obeys Property 2 above and need not obey Property 1.
Therefore, a problem is NP-complete if it is both NP and NP-hard.

Figure 1: NP Complete, P problems

Figure 2: NP Complete Complexity Classes

1.1.3 Decision vs Optimization Problems
NP-completeness applies to the realm of decision problems. It was set up this way because
it’s easier to compare the difficulty of decision problems than that of optimization
problems. In reality, though, being able to solve a decision problem in polynomial time
will often permit us to solve the corresponding optimization problem in polynomial time
(using a polynomial number of calls to the decision problem). So, discussing the difficulty
of decision problems is often really equivalent to discussing the difficulty of optimization
problems.
For example, consider the vertex cover problem (Given a graph, find out the minimum
sized vertex set that covers all edges). It is an optimization problem. The corresponding
decision problem is, given undirected graph G and k, is there a vertex cover of size k?
1.1.4 What is Reduction?
Let L1 and L2 be two decision problems. Suppose algorithm A2 solves L2. That is, if y is
an input for L2 then algorithm A2 will answer Yes or No depending upon whether y
belongs to L2 or not.
The idea is to find a transformation from L1 to L2 so that algorithm A2 can be part of
algorithm A1 to solve L1.

Figure 3: Reduction
Learning reduction, in general, is very important. For example, if we have library functions
to solve certain problems and if we can reduce a new problem to one of the solved
problems, we save a lot of time. Consider the example of a problem where we have to find
the minimum product path in a given directed graph where the product of the path is the
multiplication of weights of edges along the path. If we have code for Dijkstra’s algorithm
to find the shortest path, we can take the log of all weights and use Dijkstra’s algorithm to
find the minimum product path rather than writing a fresh code for this new problem.
1.1.5 How to prove that a given problem is NP-complete?
From the definition of NP-complete, it appears impossible to prove that a problem L is NP-
Complete. By definition, it requires us to that show every problem in NP is polynomial
time reducible to L. Fortunately, there is an alternate way to prove it. The idea is to take a
known NP-Complete problem and reduce it to L. If a polynomial-time reduction is
possible, we can prove that L is NP-Complete by transitivity of reduction (If an NP-
Complete problem is reducible to L in polynomial time, then all problems are reducible to
L in polynomial time).
1.1.6 What was the first problem proved as NP-Complete?
There must be some first NP-Complete problem proved by the definition of NP-Complete
problems. SAT (Boolean satisfiability problem) is the first NP-Complete problem proved
by Cook (See CLRS book for proof).
It is always useful to know about NP-Completeness even for engineers. Suppose you are
asked to write an efficient algorithm to solve an extremely important problem for your
company. After a lot of thinking, you can only come up exponential time approach which
is impractical. If you don’t know about NP-Completeness, you can only say that I could
not come up with an efficient algorithm. If you know about NP-Completeness and prove
that the problem is NP-complete, you can proudly say that the polynomial-time solution is
unlikely to exist. If there is a polynomial-time solution possible, then that solution solves a
big problem of computer science many scientists have been trying for years.
1.1.7 Example of NP-Complete problem
NP problem: - Suppose a DECISION-BASED problem is provided in which a set of
inputs/high inputs you can get high output.
Criteria to come either in NP-hard or NP-complete.
The point to be noted here, the output is already given, and you can verify the
output/solution within the polynomial time but can't produce an output/solution in
polynomial time.
Here we need the concept of reduction because when you can't produce an output of the
problem according to the given input then in case you have to use an emphasis on the
concept of reduction in which you can convert one problem into another problem.
So according to the given decision-based NP problem, you can decide in the form of yes or
no. If, yes then you have to do verify and convert into another problem via reduction
concept. If you are being performed, both then decision-based NP problems are in NP
compete.
Here we will emphasize NPC.

Figure 4: NP-Complete

2. BACKTRACKING
Backtracking, which is a very important skill set to solve recursive solutions. Recursive
functions are those that calls itself more than once. Consider an example of Palindrome:
Initially, the function isPalindrome(S, 0, 8) is called once with the parameters
isPalindrome(S, 1, 7). The recursive call isPalindrome(S, 1, 7) is called once with the
parameters isPalindrome(S, 2, 6).
Backtracking is one of the techniques that can be used to solve the problem. We can
write the algorithm using this strategy. It uses the Brute force search to solve the problem,
and the brute force search says that for the given problem, we try to make all the possible
solutions and pick out the best solution from all the desired solutions. This rule is also
followed in dynamic programming, but dynamic programming is used for solving
optimization problems. In contrast, backtracking is not used in solving optimization
problems. Backtracking is used when we have multiple solutions, and we require all those
solutions.
Backtracking name itself suggests that we are going back and coming forward; if it
satisfies the condition, then return success, else we go back again. It is used to solve a
problem in which a sequence of objects is chosen from a specified set so that the sequence
satisfies some criteria.

2.1 When to use a Backtracking algorithm?

When we have multiple choices, then we make the decisions from the available choices. In
the following cases, we need to use the backtracking algorithm:

● A piece of sufficient information is not available to make the best choice, so we use
the backtracking strategy to try out all the possible solutions.

● Each decision leads to a new set of choices. Then again, we backtrack to make new
decisions. In this case, we need to use the backtracking strategy.

2.2 How does Backtracking work?

Backtracking is a systematic method of trying out various sequences of decisions until

you find out that works. Let's understand through an example.

We start with a start node. First, we move to node A. Since it is not a feasible solution
so we move to the next node, i.e., B. B is also not a feasible solution, and it is a dead-end
so we backtrack from node B to node A.

Suppose another path exists from node A to node C. So, we move from node A to
node C. It is also a dead-end, so again backtrack from node C to node A. We move from
node A to the starting node.
 Now we will check any other path exists from the starting node. So, we move from
start node to the node D. Since it is not a feasible solution so we move from node D to
node E. The node E is also not a feasible solution. It is a dead end so we backtrack from
node E to node D.

Suppose another path exists from node D to node F. So, we move from node D to
node F. Since it is not a feasible solution and it's a dead-end, we check for another path
from node F.

Suppose another path exists from node D to node F. So, we move from node D to
node F. Since it is not a feasible solution and it's a dead-end, we check for another path
from node F.

Suppose there is another path exists from the node F to node G so move from node
F to node G. The node G is a success node.
The terms related to the backtracking are:

● Live node: The nodes that can be further generated are known as live nodes.

● E node: The nodes whose children are being generated and become a success node.

● Success node: The node is said to be a success node if it provides a feasible

solution.

● Dead node: The node which cannot be further generated and also does not provide
a feasible solution is known as a dead node.
Many problems can be solved by backtracking strategy, and that problems satisfy complex
set of constraints, and these constraints are of two types:

● Implicit constraint: It is a rule in which how each element in a tuple is related.

● Explicit constraint: The rules that restrict each element to be chosen from the
given set.

2.3 Applications of Backtracking

● N-queen problem
 ● Sum of subset problem

● Graph coloring

● Hamiliton cycle

3. N QUEENS PROBLEM:
N - Queens problem is to place n - queens in such a manner on an n x n chessboard that
no queens attack each other by being in the same row, column or diagonal.
It can be seen that for n =1, the problem has a trivial solution, and no solution exists for
n =2 and n =3. So first we will consider the 4 queens problem and then generate it to n -
queens problem.

3.1 4-Queens Problem

Given a 4 x 4 chessboard and number the rows and columns of the chessboard 1
through 4.
Since, we have to place 4 queens such as q1 q2 q3 and q4 on the chessboard, such that
no two queens attack each other. In such a conditional each queen must be placed on a
different row, i.e., we put queen "i" on row "i."
Now, we place queen q1 in the very first acceptable position (1, 1). Next, we put queen
q2 so that both these queens do not attack each other. We find that if we place q2 in
column 1 and 2, then the dead end is encountered. Thus the first acceptable position for q2
in column 3, i.e. (2, 3) but then no position is left for placing queen 'q3' safely. So we
backtrack one step and place the queen 'q2' in (2, 4), the next best possible solution.
 .
Figure 5: 4 X 4 Chess Board
Then we obtain the position for placing 'q3' which is (3, 2). But later this position also
leads to a dead end, and no place is found where 'q4' can be placed safely. Then we have to
backtrack till 'q1' and place it to (1, 2) and then all other queens are placed safely by
moving q2 to (2, 4), q3 to (3, 1) and q4 to (4, 3). That is, we get the solution (2, 4, 1, 3).
This is one possible solution for the 4-queens problem. For another possible solution, the
whole method is repeated for all partial solutions. The other solutions for 4 - queens
problems is (3, 1, 4, 2) i.e.

Figure 6: 4 Queen’s Problem

 The implicit tree for 4 - queen problem for a solution (2, 4, 1, 3) is as follows:
Fig shows the complete state space for 4 - queens problem. But we can use backtracking
method to generate the necessary node and stop if the next node violates the rule, i.e., if
two queens are attacking.

Figure 7: 4 Queen’s Problem

 It can be seen that all the solutions to the 4 queens problem can be represented as 4 -
tuples (x1, x2, x3, x4) where xi represents the column on which queen "qi" is placed.

Figure 8: 4 - Queens solution space with nodes numbered in DFS

3.2 8-Queen’s Problem:
The eight queens problem is the problem of placing eight queens on an 8×8 chessboard
such that none of them attack one another (no two are in the same row, column, or
diagonal). More generally, the n queens problem places n queens on an n×n chessboard.

● This pseudocode uses a backtracking algorithm to find a solution to the 8 Queen

problem, which consists of placing 8 queens on a chessboard in such a way that
no two queens threaten each other.

● The algorithm starts by placing a queen on the first column, then it proceeds to
the next column and places a queen in the first safe row of that column.

● If the algorithm reaches the 8th column and all queens are placed in a safe
position, it prints the board and returns true.

● If the algorithm is unable to place a queen in a safe position in a certain column,

it backtracks to the previous column and tries a different row.

● The “isSafe” function checks if it is safe to place a queen on a certain row and
column by checking if there are any queens in the same row, diagonal or anti-
diagonal.

● It’s worth to notice that this is just a high-level pseudocode and it might need to
be adapted depending on the specific implementation and language you are
using.
 Figure 9: 8 Queens Problem

● Thus, the solution for 8 -queen problem for (4, 6, 8, 2, 7, 1, 3, 5).

● If two queens are placed at position (i, j) and (k, l).

● Then they are on same diagonal only if (i - j) = k - l or i + j = k + l.

● The first equation implies that j - l = i - k.

● The second equation implies that j - l = k - i.

● Therefore, two queens lie on the duplicate diagonal if and only if |j-l|=|i-k|

Place (k, i) returns a Boolean value that is true if the kth queen can be placed in column i. It
tests both whether i is distinct from all previous costs x1, x2,....xk-1 and whether there is
no other queen on the same diagonal.
Using place, we give a precise solution to then n- queens problem.

Place (k, i)
{
For j 1 to k - 1
do if (x [j] = i)
or (Abs x [j]) - i) = (Abs (j - k))
then return false;
return true;
}
Place (k, i) return true if a queen can be placed in the kth row and ith column otherwise
return is false.
x [] is a global array whose final k - 1 values have been set. Abs (r) returns the absolute
value of r.
N - Queens (k, n)
{
For i 1 to n
do if Place (k, i) then
{
x [k] i;
if (k ==n) then
write (x [1....n));
else
N - Queens (k + 1, n);
}
}
4. Sum of Subsets problem
It is one of the most important problems in complexity theory. The problem is given an
A set of integers a1, a2,…., an upto n integers. The question arises that is there a non-
empty subset such that the sum of the subset is given as M integer?. For example, the set is
given as [5, 2, 1, 3, 9], and the sum of the subset is 9; the answer is YES as the sum of the
subset [5, 3, 1] is equal to 9. This is an NP-complete problem again. It is the special case of
knapsack
Let's understand this problem through an example.
problem.
We have a set of 5 integers given below:
N = 4, -2, 2, 3, 1
We want to find out the subset whose sum is equal to 5. There are many solutions to this
problem.
The naïve approach, i.e., brute-force search generates all the possible subsets of the
original array, i.e., there are 2n possible states. Here the running time complexity would be
exponential. Then, we consider all these subsets in O(N) linear running time and checks
whether the sum of the items is M or not.
The dynamic programming has pseudo-polynomial running time.
Statement: Given a set of positive integers, and a value sum, determine that the sum of the
subset of a given set is equal to the given sum.
Or
Given an array of integers and a sum, the task is to have all subsets of given array with sum
equal to the given sum.

There are two ways of solving the subset problem:

● Recursion

● Dynamic programming

4.1 Method 1: Recursion

Before knowing about the recursive approach, we should know about two things in
a subset which are given below:

● Include: Here include means that we are selecting the element from the array.

● Exclude: Here, exclude means that we are rejecting the element from the array.

To implement the recursive approach, we consider the following two cases:

Now we consider the first element and now the required sum is equal to the difference
between the target sum and value of first element. The number of elements is equal to the
difference between the total elements and 1.
Leave the 'first' element and now the required sum = target sum. The number of elements is
equal to the difference between the total elements and 1.
Let's understand that how can we solve the problem using recursion. Consider the array
which is given below:
arr = [3, 4, 5, 2]
sum = 9
result = []
In the above example, we have taken an array, and the empty array named result that stores
all the values whose resultant sum is equal to 9.
First element in an array is 3. There are two scenarios:
 ● First scenario is select. The sum is equal to the target sum - value of first element,
i.e., 9 - 3 = 6 and the first element, i.e., 3 gets stored in the result array,
i.e., result[].

● Second scenario is reject. The array arr contains the elements 4, 5, 2, i.e., arr = [4,
5, 2] and sum would be same as 9 as we are rejecting the element 3.
The result[] array would remain empty.

Now we perform the same select and reject operation on element 4 as it is the first element
of the array now.

● Select the element 4 from the array. Since we are selecting 4 from the array so array
arr would contain the elements 5, 2, i.e., arr = [5, 2]. The sum is equal to the 6-4 = 2
and the element 4 gets stored in the result arr. The result[] = {3, 4}.

● Reject the element 4 from the array. Since we are rejecting the 4 from the array so
array arr would contain the elements 5, 2, i.e., arr = [5, 2]. The sum would remain
same as 6 and the result array would be same as previous, i.e., {3}.
Now we perform the select and reject operation on element 5.

● Select the element 5 from the array. Since we are selecting 5 from the array so array
arr would contain the elements 2, i.e., arr = [2]. The sum is equal to the 2 - 5 equals
to -3 and the element 5 gets stored in the result arr. The result[] = {3, 4, 5}.

● Reject the element 5 from the array. Since we are rejecting 5 from the array so
array arr would contain the element 2, i.e., arr = [2]. The sum would remain same
as previous, i.e., 6 and the result array would be same as previous, i.e., {3, 4}.

If we observe S-5, we can see that the sum is negative that returns false. It means that there
is no further subset available in the set.

Consider R-5. It also has two scenarios:

● Select the element 2 from the array. Once the element 2 gets selected, the array
becomes empty, i.e., arr[] = " ". The sum would be 2-2 equals to 0 and the
element 2 gets stored in the result array. The result[] = [3, 4, 2].

● Reject the element 2 from the array. Once the element 2 gets rejected, the array
becomes empty, i.e., arr[] = " ". The sum would be same as previous, i.e., 2 and
the result array would also be same as previous, i.e., [3, 4].

Consider R-4. It has two scenarios:

 ● Select the element 5 from the array. Since we are selecting 5 from the array so
array arr would contain the elements 2, i.e., arr = [2]. The sum would be 6-5
equals to 1 and the element 5 gets stored in the result array. The result[] = [3, 5].
● Reject the element 5 from the array. Since we are rejecting 5 from the array so
array arr would contain the element 2, i.e., arr = [2]. The sum would remain
same as previous, i.e., 6 and the result array would be same as previous, i.e.,
{3}.

Consider S-5. It has two scenarios:

● Select the element 2 from the array. Since we are selecting 2 from the array so array arr
would be empty, i.e., arr = " ". The sum would be 1-2 equals to -1 and the element 2
gets stored in the result array. The result[] = [3, 5, 2].

● Reject the element 2 from the array. Since we are rejecting 2 from the array so array arr
would become empty. The sum would remain same as previous, i.e., 1 and the result
array would be same as previous, i.e., {3, 5}.
Consider R-5. It has two scenarios:

● Select the element 2 from the array. Since we are selecting 2 from the array so array
arr would be empty, i.e., arr = " ". The sum would be 6-2 equals to 4 and the
element 2 gets stored in the result array. The result[] = [3, 2].

● Reject the element 2 from the array. Since we are rejecting 2 from the array so
array arr would become empty. The sum would remain same as previous, i.e., 6 and
the result array would be same as previous, i.e., {3}.
Similarly, we get the reject case, i.e., R-3 as shown as below:
4.2 Method 2: Dynamic Programming

Let A be an array or set which contains 'n' non-negative integers. Find a subset 'x'
of set 'A' such that the sum of all the elements of x is equal to w where x is another input
(sum).

For example:

A = {1, 2, 5, 9, 4}

Sum(w) = 18

Now we have to find out the subset from the given set whose sum is equal to 18. Here we
will use the dynamic programming approach to solve the subset sum problem.

Example:

A = [2, 3, 5, 7, 10]

Sum(w) = 14

First, we create a table. The column contains the values from 0 to 14 while row contains
the elements of the given set shown as below:
In the below table:

i: It represents the rows. Rows represents the elements.

j: It represents the columns. Columns represent the sum.

Consider the element 2. We will use 1 as a true value and 0 as a false value. The value 1
comes under 0 and 2 columns shown as below:

Here i=1, a[i] =2

When j= 1

Required sum = 1 - 2 = -1; Since the sum is negative so put 0 under the column 1 as
shown in the above table.

When j= 2

Required sum = 2 - 2 = 0; Since the value of sum is zero so we put 1 under the column 2
as shown in the above table.

We put 0 under the columns whose sum is greater than 2 as we cannot make sum more
than 2 from the element 2.

Consider the element 3.

Here i = 2, a[i] = 3
The columns whose sum is less than 3 will have the same values as the previous columns.

When j = 3, sum[j] = 3

Required sum = 3 -3 = 0; since the sum is zero so we put 1 under the column 3 as shown
in the above table.

When j = 4; sum[j] = 4

Required sum = 4 - 3 = 1; Since the sum is 1 so we move to the previous row, i.e., i=1 and
j=1. The value at a[1][1] is 0 so we put 0 at a[2][4].

When j = 5, sum[j] = 5

Required sum = 5 -3 = 2; The value of sum is 2 so the value at a[1][2] equals to 1.

Therefore, the value at a[2][5] would be 1.

When j = 6, sum[j] = 6

Required sum = 6 -3 = 3; The value of sum is 3 so the value at a[1][3] equals to 0.

Therefore, the value at a[2][6] would be 0.

When j = 7, sum[7] = 7

Required sum = 7 - 3 = 4; The value of sum is 4 so the value at a[1][4] equals to 0.

Therefore, the value at a[2][7] would be 0.

In this way, we get the value 0 from the columns 8 to 14.

Consider the element 5.

Here i=3, a[i] = 5

The columns whose sum is less than 5 will have the same values as the previous columns.

When j =5, sum[j] = 5

Required sum = 5-5 = 0; Since the value of sum is 0; therefore, the value at a[2][5] equals
to 1.

When j = 6, sum[j] = 6

Required sum = 6-5 = 1; the value of sum is 1 so the value at a[2][1] equals to 0; therefore,
the value at a[3][6] equals to 0.

When j=7, sum[j] = 7

Required sum = 7-5 = 2; the value of sum is 2 so the value at a[2][2] equals to 1; therefore,
the value at a[3][7] equals to 1.

When j=8, sum[j] = 8

Required sum = 8-5 = 3; the value of sum is 3 so the value at a[2][3] equals to 1; therefore,
the value at a[3][8] equals to 1.

When j=9, sum[j] =9

Required sum= 9-5 = 4; the value of sum is 4 so the value at a[2][4] equals to 0; therefore
the value at a[3][9] equals to 0.

In this way, we get the values from the columns 10 to 14.

Consider the element 7.

Here i=4, a[i] =7

The columns whose sum is less than 7 will have the same values as the previous columns.

When j=9, sum[j] = 9

Required sum = 9 - 7 = 2; the value of sum is 2 so the value at a[3][2] equals to 1; therefore
the value at a[4][9] equals to 1.

When j=10, sum[j] = 10

Required sum = 10 - 7= 3; the value of sum is 3 so the value at a[3][3] equals to 1;

therefore, the value at a[4][10] equals to 1.

When j=11, sum[j] =11

Required sum = 11-7 = 4; the value of sum is 4 so the value at a[3][4] equals to 0;
therefore, the value at a[4][11] equals to 0.

When j=12, sum[j] = 12

Required sum = 12-7 = 5; the value of sum is 5 so the value at a[3][5] equals to 1;
therefore, the value at a[4][12] equals to 1.

When j=13, sum[j] =13

Required sum= 13 - 7 = 6; the value of sum is 6 so the value at a[3][6] equals to 0;

therefore, the value at a[4][13] equals to 0.

When j=14, sum[j] = 14

Required sum = 14 - 7 = 7; the value of sum is 7 so the value at a[3][7] equals to 1;

therefore, the value at a[4][14] equals to 1.

Consider the element 10

Here i=5, a[i] = 10

The columns whose sum is less than 10 will have the same values as the previous columns.

When j = 10, sum[j] = 10

Required sum = 10 - 10 = 0; the value of sum is 0 so the value at a[4][0] equals to 1;

therefore, the value at a[5][10] equals to 1.

When j = 11, sum[j] = 11

Required sum = 11 - 10 = 1; the value of sum is 1 so the value at a[4][1] equals to 0;

therefore, the value at a[5][11] equals to 0.

When j=12, sum[j] = 12

Required sum = 12-10 = 2; the value of sum is 2 so the value at a[4][2] equals to 1;
therefore, the value at a[5][12] equals to 1.

When j=13, sum[j] = 13

Required sum = 13 - 10 = 3; the value of sum is 3 so the value at a[4][3] equals to 1;

therefore, the value at a[5][13] equals to 1.

To determine whether the above given problem contains the subset or not, we need to
check the last row and the last column. If the value is 1 which means that there would exist
atleast one subset.

We have basically followed three conditions where we write 1 in the cell of the table:
● A[i] = j

● A[i-1][j] = 1

● A[i-1][j-A[i]] = 1